//
// Created by Barichek on 20.07.2023 12:22:31
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

//#define Energy_is_not_over

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1000+10, inf = 1000111222;

int n,m;
vector<pii> reb[max_n];
vector<pair<pii,int>> edges[max_n];
pair<pii,int> edge_value[max_n];

bool matr[max_n];
bitset<max_n> color_used_in_matr;

bitset<max_n> edges_with_this_color[max_n];

int X;

bool used[max_n];
int comp_id[max_n];

bitset<max_n> dfs_pref_xor[max_n];

void dfs(int now,int cur_comp_id)
{
    used[now]=1;
    comp_id[now]=cur_comp_id;
    for (auto wh:reb[now]){
        if (!used[wh.fir] && matr[wh.sec]){
            dfs_pref_xor[wh.fir]=dfs_pref_xor[now];
            dfs_pref_xor[wh.fir][wh.sec]=1;
            dfs(wh.fir,cur_comp_id);
        }
    }
}

bool green[max_n];
bool yellow[max_n];

bitset<max_n> not_used_bfs;
int pred_bfs[max_n];

bitset<max_n> cur_go_bfs;

bitset<max_n> not_matr_not_color_from_matr;

bool augment()
{
    LOG("augment");
    memset(used,0,sizeof(used));
    int comps=0;
    for (int i=0;i<n;i++){
        if (!used[i]){
            dfs_pref_xor[i].reset();
            dfs(i,comps);
            comps++;
        }
    }
    color_used_in_matr.reset();
    for (int i=0;i<m;i++){
        if (matr[i]){
            int w=edge_value[i].sec;
            assert(!color_used_in_matr[w]);
            color_used_in_matr[w]=1;
        }
    }
    for (int i=0;i<m;i++){
        if (!matr[i]){
            int u=edge_value[i].fir.fir;
            int v=edge_value[i].fir.sec;
            int w=edge_value[i].sec;
            if (w<X && !color_used_in_matr[w] && comp_id[u]!=comp_id[v]){
                color_used_in_matr[w]=1;
                matr[i]=1;
                LOG("naive",i);
                return true;
            }
        }
    }
    memset(green,0,sizeof(green));
    memset(yellow,0,sizeof(yellow));
    for (int i=0;i<m;i++){
        if (!matr[i]){
            int u=edge_value[i].fir.fir;
            int v=edge_value[i].fir.sec;
            int w=edge_value[i].sec;
            if (w<X && !color_used_in_matr[w]){
                green[i]=1;
                LOG("green",i);
            }
            if (w<X && comp_id[u]!=comp_id[v]){
                yellow[i]=1;
                LOG("yellow",i);
            }
        }
    }

    not_matr_not_color_from_matr.reset();
    for (int i=0;i<m;i++){
        if (!matr[i]){
            int w=edge_value[i].sec;
            if (w<X && !color_used_in_matr[w]){
                not_matr_not_color_from_matr[i]=1;
            }
        }
    }

    {
        not_used_bfs.reset();
        for (int i=0;i<m;i++){
            not_used_bfs[i]=1;
            pred_bfs[i]=-2;
            int w=edge_value[i].sec;
            if (w>=X){
                not_used_bfs[i]=0;
                pred_bfs[i]=-3;
            }
        }
        queue<int> q;
        for (int i=0;i<m;i++){
            if (green[i]){
                not_used_bfs[i]=0;
                q.push(i);
                pred_bfs[i]=-1;
            }
        }
        while (!q.empty()){
            int now=q.front();
            q.pop();

            LOG("bfs",now);

            int u=edge_value[now].fir.fir;
            int v=edge_value[now].fir.sec;
            int w=edge_value[now].sec;
            if (!matr[now]){
                if (yellow[now]){
                    LOG("found",now);
                    int curr=now;
                    while (curr!=-1){
                        LOG("curr",curr);
                        matr[curr]^=1;
                        curr=pred_bfs[curr];
                        assert(curr!=-2);
                        assert(curr!=-3);
                    }
                    return true;
                }
                cur_go_bfs=(not_used_bfs&(dfs_pref_xor[u]^dfs_pref_xor[v]));
                for (int i=cur_go_bfs._Find_first();i<max_n;i=cur_go_bfs._Find_next(i)){
                    not_used_bfs[i]=0;
                    q.push(i);
                    pred_bfs[i]=now;
                    LOG("bfs go first type",now,i);
                }
            }
            else{
                cur_go_bfs=(not_used_bfs&(not_matr_not_color_from_matr|edges_with_this_color[w]));
                for (int i=cur_go_bfs._Find_first();i<max_n;i=cur_go_bfs._Find_next(i)){
                    not_used_bfs[i]=0;
                    q.push(i);
                    pred_bfs[i]=now;
                    LOG("bfs go second type",now,i);
                }
            }
        }
    }
    return false;
}

bool check(int XX)
{
    X=XX;
    memset(matr,0,sizeof(matr));
    for (int i=0;i<X;i++){
        if (!augment()){
            return false;
        }
    }
    return true;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for (int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--;
        v--;
        edge_value[i]=mp(mp(u,v),w);
        edges[w].pb(mp(mp(u,v),i));
        reb[u].pb(mp(v,i));
        reb[v].pb(mp(u,i));

        edges_with_this_color[w][i]=1;
    }

    for (int i=0;i<n+10;i++){
        X=i+1;
        if (!augment()){
            cout<<i<<"\n";
            return 0;
        }
    }
    return 0;
}

/*
7 10
1 2 0
1 2 0
1 2 1
1 2 0
1 3 2
1 4 2
1 5 2
5 6 7
4 7 7
6 7 0

5 6
5 6 2
1 2 3
2 3 4
3 4 5
4 5 0
5 1 1

2 4
1 2 3
2 1 2
1 2 0
2 1 1

8 12
1 2 0
1 3 3
3 4 1
3 5 0
4 7 2
5 6 4
6 8 3
2 3 0
3 6 2
1 5 6
2 4 1
4 6 5



4 4
1 2 0
2 3 1
1 3 1
3 4 2
*/