#include <bits/stdc++.h> #define int long long #define endl "\n" #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) using namespace std; int n,m; vector<int>APR[400300]; int ctc=0; map<int,int>mp; vector<pii>g[400300]; int dep[400300]; int CTR=0; bool vis[400300]; int tp; int St[400300]; bool apnr[400300]; bool as[400300]; inline void dfs(int u,int fa){ vis[u]=1; dep[u]=dep[fa]+1; for(pii e:g[u]){ int v=p1(e),c=p2(e); if(v==fa)continue; if(!vis[v]){ St[++tp]=c; dfs(v,u); if(as[tp]==0) apnr[St[tp]]=1,as[tp]=0; else as[tp]=0; tp--; } else if(dep[v]<dep[u]){ ++CTR; APR[c].push_back(CTR); for(int i=tp;i>tp-(dep[u]-dep[v]);i--){ //assert(St[i]>0); APR[St[i]].push_back(CTR),as[i]=1; // cout<<St[i]<<" "; } //cout<<endl; } } } struct edge{ int v,w,nxt; }E[2200300]; int ecnt=1; int hd[600300],rd[600300]; int d[600300]; int S,T; inline void add(int u,int v,int w){ //cout<<u<<" "<<v<<" "<<w<<endl;; ++ecnt; E[ecnt]={v,w,hd[u]}; hd[u]=ecnt; ++ecnt; E[ecnt]={u,0,hd[v]}; hd[v]=ecnt; } inline bool BFS(){ memset(d,-1,sizeof(d)); d[S]=0; queue<int>q; q.push(S); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=hd[u];i;i=E[i].nxt){ int v=E[i].v,w=E[i].w; if(d[v]==-1&&w){ d[v]=d[u]+1; q.push(v); } } } return d[T]!=-1; } inline int DFS(int u,int fl){ if(!fl||u==T)return fl; int res=0; for(int i=rd[u];i;i=E[i].nxt){ int v=E[i].v,w=E[i].w; if(d[v]==d[u]+1&&w){ int t=DFS(v,min(fl,w)); if(v==T){ //cout<<w<<" "<<t<<endl; } E[i].w-=t; E[i^1].w+=t; fl-=t; res+=t; } if(!fl)break; rd[u]=E[i].nxt; } return res; } const int INF=1e13; inline int dinic(){ int res=0; while(BFS()){ memcpy(rd,hd,sizeof(rd)); res+=DFS(S,INF); } return res; } signed main(){ ios::sync_with_stdio(0); // freopen("b.in","r",stdin); // freopen("b.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,c; cin>>u>>v>>c; if(!mp.count(c)) mp[c]=++ctc; g[u].push_back({v,mp[c]}); g[v].push_back({u,mp[c]}); } dfs(1,0); S=ctc+CTR+1; T=ctc+CTR+2; for(int i=1;i<=ctc;i++){ if(apnr[i]) add(S,i,APR[i].size()); else add(S,i,APR[i].size()-1); for(int x:APR[i]) add(i,x+ctc,1); } for(int i=1;i<=CTR;i++) add(ctc+i,T,1); int res=dinic(); //cout<<ctc<<" "<<CTR<<" "<<res<<endl; cout<<ctc<<endl; // cout<<ctc-(CTR-res)<<endl; cout.flush(); return 0; }