#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
 
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

struct DSU
{
	int n;
	VI p, sz;
	
	void init(int _n)
	{
		n = _n;
		p.resize(n);
		iota(ALL(p), 0);
		sz.assign(n, 1);
	}
	int find(int v)
	{
		if (v == p[v])
			return v;
		return p[v] = find(p[v]);
	}
	bool unite(int u, int v)
	{
		u = find(u);
		v = find(v);
		if (u == v) 
			return false;
		if (sz[u] > sz[v])
			swap(u, v);
		p[u] = v;
		sz[v] += sz[u];
		return true;
	}
};




bool check(int n, int m, int mex, const vector<tuple<int, int, int>>& obj)
{
	VI used(m);
	int cnt = 0;	
	while(true)
	{
		//FOR(i, 0, m)
		//	cout << used[i];
		//cout << "\n";
		
		bool okOne = 0;
		DSU D;
		D.init(n);
		VI vals(mex, -1);
		FOR(i, 0, m)
		{
			auto [u, v, w] = obj[i];
			if(used[i])
			{
				assert(D.unite(u, v));
				vals[w] = i;
			}
		}
		
		VI I1(m), I2(m);
		vector<VI> g(m);
		
		FOR(i, 0, m)
		{
			auto [u, v, w] = obj[i];
			if(used[i] || w >= mex)
				continue;
			if(vals[w] == -1)
				I2[i] = 1;
			else
				g[i].PB(vals[w]);
			
			
			if(D.find(u) != D.find(v))
				I1[i] = 1;
			
			if(I1[i] && I2[i])
			{
				okOne = 1;
				used[i] = 1;
				break;
			}
		}
		if(okOne)
		{
			cnt++;
			continue;
		}
		FOR(i, 0, m)
		{
			if(!used[i])
				continue;
			D.init(n);
			FOR(j, 0, m)
			{
				auto [u, v, w] = obj[j];
				if(j != i && used[j])
					D.unite(u, v);
			}
			FOR(j, 0, m)
			{
				if(used[j])
					continue;
				auto [u, v, w] = obj[j];
				if(D.find(u) != D.find(v))
					g[i].PB(j);
			}
		}
		VI p(m, -1);
		queue<int> q;
		FOR(i, 0, m)
		{
			if(I1[i])
			{
				p[i] = i;
				q.push(i);
			}
		}
		while(!q.empty())
		{
			int v = q.front();
			q.pop();
			if(I2[v])
				break;
			for(int to : g[v])
			{
				if(p[to] == -1)
				{
					p[to] = v;
					q.push(to);
				}
			}
		}
		int v = -1;
		FOR(i, 0, m)
		{
			if(I2[i] && p[i] != -1)
				v = i;
		}
		if(v == -1)
			break;
		while(p[v] != v)
		{
			used[v] ^= 1;
			v = p[v];
		}
		used[v] ^= 1;
		cnt++;
	}
	return cnt == mex;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> g(m);
	FOR(i, 0, m)
	{
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		g[i] = {u, v, w};
	}
	//cout << check(n, m, 3, g) << "\n";
	//return 0;
	
	int L = 0, R = n + 1;
	while(R - L > 1)
	{
		int M = (L + R) / 2;
		if(check(n, m, M, g))
			L = M;
		else
			R = M;
	}
	cout << L << "\n";

	return 0;
}