#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=4e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,c[maxn]; int bel[maxn]; int hd[maxn],to[maxn],nxt[maxn],ct=1,tot; struct node { int x,y,c; }d[maxn]; void link(int x,int y){ ++ct;nxt[ct]=hd[x],hd[x]=ct,to[ct]=y; ++ct;nxt[ct]=hd[y],hd[y]=ct,to[ct]=x; } int fa[maxn],fe[maxn]; int vis[maxn],cnt,dep[maxn]; void dfs(int u){ dep[u]=dep[fa[u]]+1,vis[u]=1; for(int i=hd[u];i;i=nxt[i]){ if(to[i]==fa[u])continue; if(!vis[to[i]])fa[to[i]]=u,fe[to[i]]=i>>1,dfs(to[i]); else bel[i>>1]=++tot; } } namespace Flow { #define maxn 2500005 int hhd[maxn],hd[maxn],nxt[maxn],to[maxn],w[maxn],ct=1; void link(int x,int y,int c){ ++ct;nxt[ct]=hd[x],hd[x]=ct,to[ct]=y,w[ct]=c; ++ct;nxt[ct]=hd[y],hd[y]=ct,to[ct]=x; } int dis[maxn]; int S,T; int dfs(int u,int fl){ if(u==T)return fl; int res=0; for(int &i=hd[u];i;i=nxt[i])if(w[i]&&dis[to[i]]==dis[u]+1){ int v=dfs(to[i],min(fl,w[i])); w[i]-=v,w[i^1]+=v,fl-=v,res+=v; if(!fl)break; } if(!res)dis[u]=-1; return res; } bool bfs(){ memcpy(hd,hhd,sizeof(hd)); memset(dis,-1,sizeof(dis)); dis[S]=0;queue<int>q;q.push(S); while(!q.empty()){ int u=q.front();q.pop(); for(int i=hd[u];i;i=nxt[i])if(w[i]&&dis[to[i]]==-1)dis[to[i]]=dis[u]+1,q.push(to[i]); } return dis[T]!=-1; } int dinic(){ memcpy(hhd,hd,sizeof(hd)); int res=0; while(bfs())res+=dfs(S,1e9); return res; } #undef maxn } void slv(){ n=read(),m=read(); unordered_map<int,int>mp;int s=0; up(i,1,m){ int x=read(),y=read(),col=read(); if(!mp.count(col))mp[col]=++s;col=mp[col]; d[i].x=x,d[i].y=y,d[i].c=col; link(x,y); } up(i,1,n)if(!vis[i])dfs(i); vector<int>G; up(i,1,m)if(bel[i])G.p_b(i); for(int u:G){ int x=d[u].x,y=d[u].y; while(x!=y){ if(dep[x]>=dep[y])bel[fe[x]]=bel[u],x=fa[x]; else bel[fe[y]]=bel[u],y=fa[y]; } } mp.clear(); up(i,1,m)if(bel[i])mp[bel[i]]++; up(i,1,tot){ Flow::link(1,2+i,mp[i]-1); } up(i,1,m){ if(!bel[i])Flow::link(1,2+tot+i,1); else Flow::link(2+bel[i],2+tot+i,1); Flow::link(2+tot+i,2+tot+m+d[i].c,1); } up(i,1,s)Flow::link(2+tot+m+i,2,1); Flow::S=1,Flow::T=2; cout<<Flow::dinic(); } int main(){ //freopen("b.in","r",stdin),freopen("b.out","w",stdout); slv(); fclose(stdin),fclose(stdout); return 0; }