#include<bits/stdc++.h>
using namespace std;
const int maxn=605;
int dis[maxn][maxn],f[maxn],n,m,U[maxn],V[maxn],W[maxn],d[maxn],cnt[maxn];
vector<int> raw;
vector<int> e[maxn][maxn];
struct nodee{
	int fi,se,id;
};
vector<nodee> g[maxn];
bool vis[maxn],ismerge[maxn];
int getfa(int x){
	if(f[x]==x){
		return x;
	}
	return f[x]=getfa(f[x]);
}
struct node{
	int x,y,w,id;
	bool operator < (node aa) const{
		return w<aa.w;
	}
}b[maxn];
void dfs(int u,int fa,int root){
	for(auto v:g[u]){
		if(v.fi!=fa){
			e[root][v.fi]=e[root][u];
			if(e[root][v.fi].empty()||v.se>W[e[root][v.fi][0]]){
				e[root][v.fi].clear();
				e[root][v.fi].push_back(v.id);
			}
			else if(v.se==W[e[root][v.fi][0]]){
				e[root][v.fi].push_back(v.id);
			}
			dfs(v.fi,u,root);
		}
	}
}
int solve(int x){
	memset(vis,0,sizeof vis),memset(d,0,sizeof d);
	int s1=0,s2=0;
	for(int i=1;i<=n-x;i++){
		int maxx=0;
		for(int j=1;j<=n;j++){
			if(!ismerge[j]&&!vis[j]&&d[j]>=d[maxx]){
				maxx=j;
			}
		}
		if(i==n-x){
			s2=maxx;
			break;
		}
		else if(i==n-x-1){
			s1=maxx;
		}
		vis[maxx]=1;
		for(int j=1;j<=n;j++){
			d[j]+=dis[j][maxx];
		}
	}
	ismerge[s1]=1;
	dis[s1][s2]=dis[s2][s1]=0;
	for(int i=1;i<=n;i++){
		dis[i][s2]+=dis[i][s1];
		dis[s2][i]+=dis[s1][i];
	}
	return d[s2];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>U[i]>>V[i]>>W[i];
		b[i].x=U[i],b[i].y=V[i],b[i].w=W[i],b[i].id=i;
	}
	sort(b+1,b+m+1);
	for(int i=1;i<=m;i++){
		int xx=getfa(b[i].x),yy=getfa(b[i].y);
		if(xx!=yy){
			raw.push_back(b[i].id);
			f[xx]=yy;vis[b[i].id]=1;
			g[b[i].x].push_back({b[i].y,b[i].w,b[i].id}),g[b[i].y].push_back({b[i].x,b[i].w,b[i].id});
		}
	}
	for(int i=1;i<=n;i++){
		dfs(i,0,i);
	}
	for(int i=1;i<=m;i++){
		if(!vis[i]){
			if(W[i]==W[e[U[i]][V[i]][0]]){
				for(auto v:e[U[i]][V[i]])cnt[v]++;
				vis[i]=1;
			}
		}
	}
	for(auto v:raw){
		if(cnt[v]==0){
			cout<<"1";
			return 0;
		}
	}
	for(int i=1;i<=m;i++){
		if(vis[i]){
			dis[U[i]][V[i]]++,dis[V[i]][U[i]]++;
		}
	}
	int ans=m+1;
	for(int i=1;i<n;i++){
		ans=min(ans,solve(i-1));
	}
	cout<<ans;
	return 0;
}
/*
2 5
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
*/