#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define N 2000
#define M 4000000
#define inf 1e9
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],lg[N+1],pv[N+1],c[N+1],X[N+1],Y[N+1],Z[N+1],cnt[N+1];
bool used[N+1],vis[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()
{
    len=0;
    for (int i=s;i<=t;++i) vis[i]=pv[i]=0,E[i].clear();
    for (int i=0;i<=m;++i) cnt[i]=0;
    for (int i=1;i<=n;++i) rt[i]=i;
    for (int i=1;i<=m;++i)
	if (used[i])
	{
	    cnt[Z[i]]++;
	    if (find(X[i])!=find(Y[i])) unionn(find(X[i]),find(Y[i]));
	}
    for (int i=1;i<=m;++i)
	if (!used[i])
	{
	    cnt[Z[i]]++;
	    if (cnt[Z[i]]<=c[Z[i]]) add(s,i);
	    cnt[Z[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])
		{
		    cnt[Z[i]]--,cnt[Z[j]]++;
		    if (cnt[Z[j]]<=c[Z[j]]) add(i,j);
		    cnt[Z[i]]++,cnt[Z[j]]--;
		    if (find(X[j])!=find(Y[j])) add(j,i);
		}
	}
    return;
}
bool find_rd()
{
    int top;
    add_edge();
    queue<int>q;
    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]);
    }
    return vis[t];
}
void solve()
{
    int x=pv[t];
    while (x!=s) used[x]^=1,x=pv[x];
    return;
}
bool check(int x)
{
    int res=0;
    c[x]=1,add_edge(),find_rd(),solve();
    for (int i=1;i<=m;++i) res+=used[i];
    return res==x+1;
}
int main()
{
    for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
    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;
}