#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define N_ 510000
#define SZ 524288
typedef pair<int,int> pii;
int n, m, res, C[N_], PPP[N_], Num[N_], Ed[N_], Dep[N_], ord[N_];
vector<int>E[N_], Ch[N_];
struct Edge{
int e, d;
};
int Dis[N_], par[N_], D[N_], D2[N_], chk[N_], MD2[N_];
int UD[N_], UD2[N_], UMD2[N_];
int MM1[N_][4], MM2[N_][4];
int MPV1[N_][4], MPV2[N_][4];
struct AA{
int a, b, c;
};
void DFS(int a, int pp, int d){
Dis[a]=d;
par[a]=pp;
for(auto &x : E[a]){
if(x!=pp)DFS(x,a,d+1);
}
}
void DFS2(int a, int pp){
D[a]=D2[a]=MD2[a]=0;
par[a]=pp;
C[a]=1;
for(auto &x : E[a]){
if(x==pp||chk[x])continue;
Dep[x]=Dep[a]+1;
DFS2(x,a);
C[a]+=C[x];
D2[a]=max(D2[a],D[a]+D[x]+1);
D[a]=max(D[a],D[x]+1);
MD2[a]=max(MD2[a],MD2[x]);
}
MD2[a]=max(MD2[a],D2[a]);
}
void UDT(int *M, int *pv, int a, int b, int sz){
int i, j;
for(i=0;i<sz;i++){
if(M[i]<a){
for(j=sz-1;j>i;j--){
M[j]=M[j-1];
pv[j]=pv[j-1];
}
M[i]=a,pv[i]=b;
break;
}
}
}
void DFS3(int a, int pp){
for(auto &x : E[a]){
if(x==pp)continue;
Ch[a].push_back(x);
}
int Mx[3]={-5,-5,-5},px[3]={-1,-1,-1};
int Mx2[2]={-1,-1}, px2[2]={-1,-1};
if(pp){
UDT(Mx,px,UD[a],pp,3);
UDT(Mx2,px2,UMD2[a],pp,2);
}
UDT(Mx,px,-1,a,3);
for(auto &x : Ch[a]){
UDT(Mx, px, D[x],x,3);
UDT(Mx2,px2,MD2[x],x,2);
}
int i;
for(auto &x : Ch[a]){
int d1=-1,d2=-1;
int M1=-5,M2=-5;
for(i=0;i<3;i++){
if(px[i]!=x){
if(M1==-5)M1=Mx[i];
else if(M2==-5)M2=Mx[i];
}
}
for(i=0;i<2;i++){
if(px2[i]!=x){
d2=Mx2[i];
break;
}
}
UD[x]=M1+1;
d2=max(d2,UD[x]);
if(M1!=-5 && M2!=-5)d2=max(d2, M1+M2+2);
UMD2[x] = d2;
}
for(auto &x : Ch[a])DFS3(x,a);
}
pii Calc(int a, int p1, int p2){
int i, r2=0;
int z1=-1,z2=-1;
for(i=0;i<4;i++){
if(MPV1[a][i]!=p1&&MPV1[a][i]!=p2){
if(z1==-1)z1=MM1[a][i];
else if(z2==-1)z2=MM1[a][i];
}
if(MPV2[a][i]!=p1&&MPV2[a][i]!=p2){
r2=max(r2,MM2[a][i]);
}
}
if(z1!=-1 && z2!=-1)r2 = max(r2,z1+z2);
if(z1<0)z1=0;
return pii(z1,r2);
}
int cnt;
void HLD(int a, int ppp){
Num[a]=++cnt;
ord[cnt]=a;
PPP[a]=ppp;
int Mx=-1,pv=-1;
for(auto &x : Ch[a]){
if(Mx<C[x]){
Mx=C[x],pv=x;
}
}
if(pv!=-1){
HLD(pv,ppp);
}
for(auto &x : Ch[a]){
if(pv!=x)HLD(x,x);
}
Ed[a]=cnt;
}
pii DD[N_], DD2[N_], DD3[N_];
int Pre2[N_], DPre[N_];
struct BB{
int top, bot;
}Pre1[N_];
struct Node{
int top, bot;
int g;
int d2;
}IT[SZ+SZ];
int INF = 1e9;
Node Merge(Node a, Node b){
Node r;
r.top=max(a.top,b.top);
r.bot=max(a.bot,b.bot);
r.g=max(max(a.g,b.g),a.top+b.bot);
r.d2=max(a.d2,b.d2);
return r;
}
Node GetNode(int b, int e){
b+=SZ,e+=SZ;
vector<int>A,B;
while(b<=e){
if(b&1)A.push_back(b);
if(!(e&1))B.push_back(e);
b=(b+1)>>1,e=(e-1)>>1;
}
reverse(B.begin(),B.end());
int ck=0;
Node res;
for(auto &t : A){
if(!ck){
ck=1;
res=IT[t];
continue;
}
else res=Merge(res,IT[t]);
}
for(auto &t : B){
if(!ck){
ck=1;
res=IT[t];
continue;
}
else res=Merge(res,IT[t]);
}
return res;
}
void ITPut(int a, int tt, int bb, int d2){
a+=SZ;
IT[a]={tt,bb,-INF,d2};
while(a!=1){
a>>=1;
IT[a]=Merge(IT[a*2],IT[a*2+1]);
}
}
int LCA(int a, int b){
while(PPP[a]!=PPP[b]){
if(Num[PPP[a]]<Num[PPP[b]])b=par[PPP[b]];
else a=par[PPP[a]];
}
if(Dep[a]<Dep[b])return a;
return b;
}
int MM;
int GoPath(int a, int l, int &cl){
int t = a, bef = -1;
int MB = -1e9;
while(1){
if(t==l){
cl=bef;
break;
}
pii z;
int bb, ee;
if(a==t){
z = DD3[a];
}
else{
z = DD2[bef];
}
MM=max(MM,z.second);
int bot1 = z.first-Dep[t]+1,top1=z.first+Dep[t]+1;
MM=max(MM,top1+MB);
MB=max(MB,bot1);
if(PPP[t]==PPP[l]){
bb = Num[l]+1, ee = Num[t] - 1;
cl=ord[bb];
if(bb<=ee){
Node tp = GetNode(bb,ee);
MM=max(MM,max(tp.g,tp.d2));
MM=max(MM, MB+tp.top);
MB=max(MB,tp.bot);
}
break;
}
else{
bb = Num[PPP[t]], ee = Num[t] - 1;
if(bb<=ee){
MM=max(MM,Pre2[ee]);
MM=max(MM,DPre[ee]);
MM=max(MM,MB+Pre1[ee].top);
MB=max(MB,Pre1[ee].bot);
}
}
bef = PPP[t];
t=par[PPP[t]];
}
return MB;
}
void Go(int a, int b, int c){
int l = LCA(a,b);
MM=-1e9;
int ca=-1,cb=-1;
int MB1 = GoPath(a,l,ca);
int MB2 = GoPath(b,l,cb);
pii zz = Calc(l,ca,cb);
MM=max(MM,zz.second);
int tt = zz.first+Dep[l]+1;
// printf("%d\n",MM);
// printf("%d %d\n",DD3[5].first,DD3[5].second);
// printf("%d %d\n",MB1,MB2);
MM=max(MM,max(MB1,MB2)+tt);
// printf("%d %d %d %d\n",MB1,MB2,ca,cb);
MM=max(MM,MB1+MB2+Dep[l]*2);
// printf("%d %d %d\n",a,b,l);
int base = 2*(n-1)+c-(Dep[a]+Dep[b]-Dep[l]*2);
// printf("%d %d %d %d\n",a,b,base,MM);
res=min(res,base-MM);
}
int main(){
int i, a, b, c, j;
scanf("%d%d",&n,&m);
vector<AA>V;
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
a++,b++;
if(c==1){
E[a].push_back(b);
E[b].push_back(a);
}
else{
V.push_back({a,b,c});
}
}
DFS(1,0,0);
int Mx=-1, x=-1, y=-1;
for(i=1;i<=n;i++)if(Mx < Dis[i])Mx=Dis[i],x=i;
DFS(x,0,0);
Mx=-1;
for(i=1;i<=n;i++)if(Mx < Dis[i])Mx=Dis[i],y=i;
res = 2*(n-1)-Mx;
DFS2(1,0);
DFS3(1,0);
HLD(1,1);
for(i=1;i<=n;i++){
for(j=0;j<4;j++){
MM1[i][j]=MM2[i][j]=MPV1[i][j]=MPV2[i][j]=-1;
}
for(auto &x : E[i]){
int d = D[x]+1;
if(x==par[i])d = UD[i]+1;
UDT(MM1[i],MPV1[i],d,x,4);
d = MD2[x];
if(x==par[i])d = UMD2[i];
UDT(MM2[i],MPV2[i],d,x,4);
}
}
for(i=2;i<n;i++){
int x = ord[i];
int y = ord[i+1];
DD[x]=Calc(x,y,par[x]);
}
for(x=1;x<=n;x++){
if(par[x])DD2[x] = Calc(par[x],x,par[par[x]]);
DD3[x] = Calc(x,par[x],-1);
}
for(i=1;i<=n;i++){
int x = ord[i];
int z = PPP[x];
int tt = DD[x].first + Dep[x] + 1;
int bb = DD[x].first - Dep[x] + 1;
if(x==z){
Pre1[i]={tt,bb};
Pre2[i] = DD[x].second;
DPre[i]=-INF;
}
else{
DPre[i]=max(DPre[i-1],bb+Pre1[i-1].top);
Pre1[i]={max(tt,Pre1[i-1].top), max(bb,Pre1[i-1].bot)};
Pre2[i] = max(Pre2[i-1],DD[x].second);
}
ITPut(i,tt,bb,DD[x].second);
}
for(auto &t : V){
Go(t.a,t.b,t.c);
}
printf("%d\n",res);
}
