#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define N 2000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int n,m,d,s,t,len,rt[N+1],pv[N+1],X[N+1],Y[N+1],Z[N+1],cnt[N+1];
bool used[N+1],vis[N+1],vst[N+1];
vector<int>E[N+1];
void add(int x,int y)
{
    E[x].push_back(y);
    return;
}
int find(int x)
{
    if (rt[x]==x) return x;
    return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
    rt[x]=y;
    return;
}
void add_edge()
{
    for (int i=s;i<=t;++i) pv[i]=0,E[i].clear();
    for (int i=0;i<=m;++i) vst[i]=(i<=d);
    for (int i=1;i<=n;++i) rt[i]=i;
    for (int i=1;i<=m;++i)
	if (used[i])
	{
	    vst[Z[i]]=1;
	    if (find(X[i])!=find(Y[i])) unionn(find(X[i]),find(Y[i]));
	}
    for (int i=1;i<=m;++i)
	if (!used[i])
	{
	    if (!vst[Z[i]]) add(s,i);
	    if (find(X[i])!=find(Y[i])) add(i,t);
	}
    for (int i=1;i<=m;++i)
	if (used[i])
	{
	    for (int j=1;j<=n;++j) rt[j]=j;
	    for (int j=1;j<=m;++j)
		if (used[j]&&find(X[j])!=find(Y[j])&&j!=i)
		    unionn(find(X[j]),find(Y[j]));
	    for (int j=1;j<=m;++j)
		if (!used[j])
		{
		    if (Z[i]==Z[j]||!vst[Z[j]]) add(i,j);
		    if (find(X[j])!=find(Y[j])) add(j,i);
		}
	}
    return;
}
bool find_rd()
{
    int top;
    queue<int>q;
    for (int i=s;i<=t;++i) vis[i]=0;
    q.push(s),vis[s]=1;
    while (!q.empty())
    {
	top=q.front(),q.pop();
	for (int i=0;i<E[top].size();++i)
	    if (!vis[E[top][i]])
	    {
		vis[E[top][i]]=1,pv[E[top][i]]=top,q.push(E[top][i]);
		if (E[top][i]==t) return 1;
	    }
    }
    return 0;
}
void solve()
{
    int x=pv[t];
    while (x!=s) used[x]^=1,x=pv[x];
    return;
}
bool check(int x)
{
    d=x,add_edge();
    if (!find_rd()) return 0;
    solve();
    return 1;
}
int main()
{
    n=read(),m=read(),s=0,t=m+1;
    for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read();
    for (int i=0;i<=m;++i)
	if (!check(i))
	{
	    printf("%d\n",i);
	    return 0;
	}
    return 0;
}