//verification of Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (2019-09-01). "Exact and approximation algorithms for weighted matroid intersection". Mathematical Programming. 177 (1): 85–112. doi:10.1007/s10107-018-1260-x. hdl:2324/1474903. ISSN 1436-4646. S2CID 254138118.
//based on https://qoj.ac/submission/548815
#include <bits/stdc++.h>
// #include"C:/code/deb_20.cpp"
using ll = long long;
using i128=__int128;
using ld = long double;
#define int ll
template<typename T>using V=std::vector<T>;
using vi=V<int>;
using vvi=V<vi>;
using namespace std;
constexpr ll M=ll(1e18)+9;

#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)

template<typename T, typename A, typename B>
vector<T> matroid_intersection(const vector<T>& ground_set, const A& matroid1, const B& matroid2) {
    int n = ground_set.size();
    vector<char> in_set(n), in_matroid1(n), in_matroid2(n);
    vector<bool> used(n);
    vector<int> par(n), left, right;
    left.reserve(n);
    right.reserve(n);

    while (true) {
        A m1 = matroid1;
        B m2 = matroid2;
        left.clear();
        right.clear();
        for (int i = 0; i < n; i++) {
            if (in_set[i]) {
                m1.add(ground_set[i]);
                m2.add(ground_set[i]);
                left.push_back(i);
            } else {
                right.push_back(i);
            }
        }

        fill(all(in_matroid1), 0);
        fill(all(in_matroid2), 0);
        bool found = false;
        for (int i : right) {
            in_matroid1[i] = m1.independed_with(ground_set[i]);
            in_matroid2[i] = m2.independed_with(ground_set[i]);
            if (in_matroid1[i] && in_matroid2[i]) {
                in_set[i] = 1;
                found = true;
                break;
            }
        }

        if (found) {
            continue;
        }

        fill(all(used), false);
        fill(all(par), -1);
        queue<int> que;
        for (int i : right) {
            if (in_matroid1[i]) {
                used[i] = true;
                que.push(i);
            }
        }

        while (!que.empty() && !found) {
            int v = que.front();
            que.pop();

            if (in_set[v]) {
                A m = matroid1;
                for (auto i : left) {
                    if (i != v) {
                        m.add(ground_set[i]);
                    }
                }

                for (auto u : right) {
                    if (!used[u] && m.independed_with(ground_set[u])) {
                        par[u] = v;
                        used[u] = true;
                        que.push(u);

                        if (in_matroid2[u]) {
                            found = true;
                            for (; u != -1; u = par[u]) {
                                in_set[u] ^= 1;
                            }
                            break;
                        }
                    }
                }
            } else {
                B m = m2;
                m.add_extra(ground_set[v]);
                for (auto u : left) {
                    if (!used[u] && m.independed_without(ground_set[u])) {
                        par[u] = v;
                        used[u] = true;
                        que.push(u);
                    }
                }
            }
        }

        if (!found) {
            break;
        }
    }

    vector<T> res;
    for (int i = 0; i < n; i++) {
        if (in_set[i]) {
            res.push_back(ground_set[i]);
        }
    }
    return res;
}

struct item {
    int v, u, w;
};

struct colorful_matroid {
    vector<int> cnt;
    int cnt_bad = 0;

    colorful_matroid(int n) : cnt(n + 1) {}

    void add(const item& item) {
        auto x = item.w;
        assert(cnt[x] == 0);
        cnt[x]++;
    }

    bool independed_with(const item& item) const {
        auto x = item.w;
        return cnt[x] == 0;
    }

    void add_extra(const item& item) {
        auto x = item.w;
        cnt_bad += cnt[x] == 1;
        cnt[x]++;
    }

    bool independed_without(const item& item) const {
        auto x = item.w;
        return cnt_bad == 0 || cnt[x] == 2;
    }
};

struct graph_matroid {
    vector<int> par;

    graph_matroid(int n) : par(n) {
        iota(all(par), 0);
    }

    int root(int v) {
        return par[v] == v ? v : par[v] = root(par[v]);
    }

    bool independed_with(const item& item) {
        int v = item.v, u = item.u;
        return root(v) != root(u);
    }

    void add(const item& item) {
        int v = item.v, u = item.u;
        assert(root(v) != root(u));
        par[root(v)] = root(u);
    }
};

vi&operator+=(vi&a,const vi&b){for(int i=0;i<ssize(a);++i)(a[i]+=b[i])%=M;return a;}
vi&operator*=(vi&a,const ll&b){for(auto&&x:a)x=x*i128(b)%M;return a;}
#define GEN_OP(op) auto operator op(auto a,const auto&b){return a op##= b;}
GEN_OP(+)
GEN_OP(*)
// struct Matrix:vvi{
// 	
// };
ll qpow(i128 a,auto b){ll res=1;for(;b;a=a*a%M,b>>=1)if(b&1)res=res*a%M;return res;}
using Matrix=vvi;
int rnk(Matrix a){
	int n=ssize(a),m=ssize(a[0]),i=0,j=0;
	for(;i<n&&j<m;++j){
		int r=i;
		for(;r<n;++r)if(a[r][j])break;
		if(r<n&&a[r][j]){
			if(r!=i)std::swap(a[r],a[i]);
			for(int l=i+1;l<n;++l){
				i128 fct=i128(M-a[l][j])*qpow(a[i][j],M-2);
				a[l]+=a[i]*fct;
			}
			++i;
		}
	}
	return i;
}
mt19937_64 rng(19260817);
auto rnd(auto a,auto b){return std::uniform_int_distribution(a,b)(rng);}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<item> st(m);
    for (int i = 0; i < m; i++) {
        cin >> st[i].v >> st[i].u >> st[i].w;
        st[i].v--, st[i].u--;
    }

    auto possible = [&](int mex) {
    	// if constexpr(false){
	        vector<item> cur_st;
	        for (auto item : st) {
	            if (item.w < mex) {
	                cur_st.push_back(item);
	            }
	        }
	        colorful_matroid cm(n);
	        graph_matroid g(n);
	        auto resoid=len(matroid_intersection(cur_st, g, cm));
    	// }else{
    		vvi ma(n+m,vi(mex+m));
    		for(int i=0;i<m;++i)if(st[i].w<mex){
    			ma[n+i][mex+i]=rnd(1ll,M-1);
    			auto x=rnd(1ll,M-1);
    			ma[st[i].v][mex+i]=+x;
    			ma[st[i].u][mex+i]=M-x;
    			ma[n+i][st[i].w]=1;
    		}
    		auto resix=rnk(ma);
    	// }
    	// debug(mex,resoid,resix);
    	return resix>=mex*2;
    };

    int lb = 0, rb = n + 1;
    while (rb - lb > 1) {
        int mid = (lb + rb) / 2;
        (possible(mid) ? lb : rb) = mid;
    }
    cout << lb << '\n';
}