#include <bits/stdc++.h>
using namespace std;
template<int K>
struct KMax
{
pair<int, int> data[K];
KMax()
{
reset();
}
void reset()
{
for(int i=0; i<K; i++)
data[i]={-1, 0};
}
void insert(int k, int v)
{
for(int i=0; i<K; i++) if(data[i].second<v)
{
for(int j=K-2; j>=i; j--)
data[j+1]=data[j];
data[i]={k, v};
break;
}
}
int get(int ban, int k)
{
int ret=0;
for(int i=0; i<K; i++) if(data[i].first!=ban)
{
ret+=data[i].second;
if(--k==0)
break;
}
return ret;
}
int get(int ban1, int ban2, int k)
{
int ret=0;
for(int i=0; i<K; i++) if(data[i].first!=ban1 && data[i].first!=ban2)
{
ret+=data[i].second;
if(--k==0)
break;
}
return ret;
}
};
struct edge
{
int u, v, w;
};
int N;
vector<vector<int>> adj;
vector<edge> q, qb;
vector<int> qc;
vector<int> sz;
vector<int> depth;
vector<int> tin;
vector<int> invt;
int tnow;
vector<int> subtree;
vector<int> lpath; // longest path in this subtree
vector<int> lerased; // longest path from an erased subtree next to this, includes erased edge
vector<int> leraseddiam; // longest diameter from an erased subtree next to this
vector<int> ldiam; // longest diameter in this subtree
// type 0
// . (. .) (c)
// (.)
// /|
vector<int > type0; // longest path off the main path
// type 1
// (- -) - (. .) . (c)
// |
vector<int> type1;
void dfs_type012(int u, int p, int max_t0, int max_t1, int max_p2, int max_t2)
{
type0[u]=max(max_t0, ldiam[u]);
type1[u]=max(max_t1, lpath[u]);
KMax<2> m2d;
for(auto& v: adj[u]) if(v!=p)
m2d.insert(v, ldiam[v]);
KMax<3> m3;
m3.insert(u, lerased[u]);
for(auto& v: adj[u]) if(v!=p)
m3.insert(v, lpath[v]+1);
for(auto& v: adj[u]) if(v!=p)
{
int w=m3.get(v, 1);
dfs_type012(v, u, max(max_t0, max(m2d.get(v, 1), m3.get(v, 2))),
max(max_t1, w)+1,
max(max_p2, w+depth[u]), max(max_t2, w+max_p2)+1);
}
}
pair<int, int> dfs(int u, int p)
{
pair<int, int> ret={u, 0};
for(auto& v: adj[u]) if(v!=p)
{
int a, b;
tie(a, b)=dfs(v, u);
if(b+1>ret.second)
ret={a, b+1};
}
return ret;
}
void dfs_sz(int u, int p)
{
sz[u]=1;
for(auto& v: adj[u]) if(v!=p)
{
dfs_sz(v, u);
sz[u]+=sz[v];
}
}
void dfs_t(int u, int p)
{
tin[u]=tnow++;
invt[tin[u]]=u;
lpath[u]=lerased[u];
ldiam[u]=leraseddiam[u];
for(auto& v: adj[u]) if(v!=p)
{
depth[v]=depth[u]+1;
dfs_t(v, u);
lpath[u]=max(lpath[u], lpath[v]+1);
ldiam[u]=max(ldiam[u], ldiam[v]);
}
KMax<2> m2;
m2.insert(u, lerased[u]);
for(auto& v: adj[u]) if(v!=p)
m2.insert(v, lpath[v]+1);
ldiam[u]=max(ldiam[u], m2.data[0].second+m2.data[1].second);
}
int get_centroid(int u)
{
while(1)
{
int w=-1;
for(auto& v: adj[u]) if(w==-1 || sz[v]>sz[w])
w=v;
if(w==-1 || sz[w]*2<=sz[u])
break;
sz[u]-=sz[w];
sz[w]+=sz[u];
u=w;
}
return u;
}
int solve(int u, int ql, int qr)
{
if(ql==qr)
return 0x3f3f3f3f;
dfs_sz(u, u);
u=get_centroid(u);
tnow=0;
depth[u]=0;
dfs_t(u, u);
int last=tin[u], lastu=u;
for(auto& v: adj[u])
{
for(int i=last; i<tin[v]; i++)
subtree[invt[i]]=lastu;
last=tin[v];
lastu=v;
}
for(int i=last; i<tnow; i++)
subtree[invt[i]]=lastu;
type0[u]=type1[u]=0;
KMax<3> m3;
KMax<4> m4;
m4.insert(-1, lerased[u]);
for(auto& v: adj[u])
{
qc[v]=0;
m3.insert(v, ldiam[v]);
m4.insert(v, lpath[v]+1);
dfs_type012(v, u, 0, 0, 0, 0);
}
int qo=ql, qp=ql;
int ret=0x3f3f3f3f;
for(; ql<qr; ql++)
{
if(subtree[q[ql].u]==subtree[q[ql].v])
{
qc[subtree[q[ql].u]]++;
q[qp++]=q[ql];
continue;
}
int u=q[ql].u, v=q[ql].v, w=q[ql].w;
// 3 cases:
// 1. full cycle
ret=min(ret, 2*(N-1+w)-depth[u]-depth[v]-w-max(max(type0[u], type0[v]), max(m3.get(subtree[u], subtree[v], 1), m4.get(subtree[u], subtree[v], 2))));
// 2. partial cycle (gap on different sides)
ret=min(ret, 2*(N-2+w)-w-type1[u]-type1[v]);
// 3. partial cycle (gap on same side)
// 3c. on u's side, v's end on centroid
ret=min(ret, 2*(N-2+w)-w-type1[u]-depth[v]-m4.get(subtree[u], subtree[v], 1));
// 3d. on v's side, u's end on centroid
ret=min(ret, 2*(N-2+w)-w-type1[v]-depth[u]-m4.get(subtree[u], subtree[v], 1));
}
int qcs=0;
for(auto& v: adj[u])
{
qcs+=qc[v];
qc[v]=qcs;
}
for(int i=qo; i<qp; i++)
qb[--qc[subtree[q[i].u]]]=q[i];
for(int i=qo; i<qp; i++)
q[i]=qb[i-qo];
vector<pair<int, int>> ival;
int l=qo, r;
for(auto& v: adj[u])
{
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
lerased[v]=max(lerased[v], m4.get(v, 1)+1);
leraseddiam[v]=max(leraseddiam[v], max(lerased[v], max(m3.get(v, 1), m4.get(v, 2))));
for(r=l; r<qp && subtree[q[r].u]==v; r++);
ival.push_back({l, r});
l=r;
}
for(int i=0; i<(int)adj[u].size(); i++)
ret=min(ret, solve(adj[u][i], ival[i].first, ival[i].second));
return ret;
}
int min_walk(int n, std::vector<int> x, std::vector<int> y, std::vector<int> w)
{
N=n;
int m=x.size();
adj.resize(n);
for(int i=0; i<m; i++) if(w[i]==1)
{
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
int ans=2*(n-1)-dfs(dfs(0, 0).first, -1).second;
for(int i=0; i<m; i++) if(w[i]>1 && x[i]!=y[i])
q.push_back({x[i], y[i], w[i]});
qb.resize(q.size());
qc.resize(n);
sz.resize(n);
depth.resize(n);
tin.resize(n);
invt.resize(n);
subtree.resize(n);
lpath.resize(n);
lerased.resize(n);
leraseddiam.resize(n);
ldiam.resize(n);
type0.resize(n);
type1.resize(n);
ans=min(ans, solve(0, 0, (int)q.size()));
return ans;
}
int main()
{
int n, m;
ignore = scanf("%d%d", &n, &m);
std::vector<int> x(m), y(m), w(m);
for(int i=0; i<m; i++)
ignore = scanf("%d%d%d", &x[i], &y[i], &w[i]);
printf("%d\n", min_walk(n, x, y, w));
return 0;
}
