#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+4, MOD = 998244353, BASE = 31;
vector<int> adj[MN];
struct Edge {
int a,b,w;
};
int sum, diam, ret, n, subREE[MN], down[MN], down2[MN], pp[MN], which[MN], up[MN], cc, comp[MN], sz[MN], depth[MN], subDiam[MN], wotDown[MN][2], wotDiam[MN], valDown[MN][3], valDiam[MN][2], case1[MN], case2[MN], case3[MN], upDiam[MN]; bool done[MN]; ll iters;
void dfs (int cur, int par = -1) {
down[cur] = down2[cur] = 0;
for (int i : adj[cur]) if (i != par) {
dfs(i,cur); ++sum;
int d = down[i] + 1;
if (d > down[cur]) {
down2[cur] = down[cur];
down[cur] = d;
} else down2[cur] = max(down2[cur],d);
}
diam = max(diam,down[cur] + down2[cur]);
}
void dfs3 (int cur, int par = -1) {
pp[cur] = par;
if (~par) up[cur] = max(up[par],cur == wotDown[par][0] ? valDown[par][1] : valDown[par][0]) + 1;
else up[cur] = 0;
for (int i : adj[cur]) if (i != par) {
dfs3(i,cur);
}
}
int solve (int rt) {
sum = 0; diam = 0;
dfs(rt);
return sum * 2 - diam;
}
int getsz (int cur, int par = -1) {
sz[cur] = 1;
for (int i : adj[cur]) if (i != par && !done[i]) {
sz[cur] += getsz(i,cur);
}
return sz[cur];
}
int getcent (int cur, int tot, int par = -1) {
for (int i : adj[cur])
if (i != par && !done[i] && sz[i] > (tot>>1))
return getcent(i,tot,cur);
return cur;
}
void godown (int cur, int par) {
depth[cur] = depth[par] + 1;
valDown[cur][0]=valDown[cur][1]=valDown[cur][2]=valDiam[cur][0]=valDiam[cur][1]=0; comp[cur] = cc;
for (int i : adj[cur]) if (i != par) {
int d,dia,who;
if (!done[i]) {
godown(i,cur);
dia = subDiam[i]; d = valDown[i][0] + 1; who = i;
} else {
if (pp[i] == cur) {
dia = subREE[i]; d = down[i] + 1;
} else {
d = up[cur]; dia = upDiam[cur];
}
who = -1;
}
if (d > valDown[cur][0]) {
valDown[cur][2] = valDown[cur][1];
valDown[cur][1] = valDown[cur][0];
valDown[cur][0] = d;
wotDown[cur][1] = wotDown[cur][0];
wotDown[cur][0] = who;
} else if (d > valDown[cur][1]) {
valDown[cur][2] = valDown[cur][1];
valDown[cur][1] = d;
wotDown[cur][1] = who;
} else valDown[cur][2] = max(valDown[cur][2],d);
if (dia > valDiam[cur][0]) {
valDiam[cur][1] = valDiam[cur][0];
valDiam[cur][0] = dia;
wotDiam[cur] = who;
} else valDiam[cur][1] = max(valDiam[cur][1],dia);
}
subDiam[cur] = max(valDiam[cur][0],valDown[cur][0] + valDown[cur][1]);
}
void goup (int cur, int par = -1, int push = 0, int push2 = 0) {
case1[cur] = max(push,subDiam[cur]); case2[cur] = max(push2,valDown[cur][0]);
for (int i : adj[cur]) if (i != par && !done[i]) {
bool go = i == wotDown[cur][0];
int direct = valDown[cur][go] + valDown[cur][1 + (go || i == wotDown[cur][1])];
int indirect = valDiam[cur][i == wotDiam[cur]];
int togo = valDown[cur][go];
case3[i] = max(case3[cur],togo+depth[cur]);
goup(i,cur,max({push,indirect,direct}),max(push2,togo) + 1);
}
}
void prep (int cur, int par = -1, int push = 0) {
upDiam[cur] = push; subREE[cur] = subDiam[cur];
push = max(push,up[cur]);
for (int i : adj[cur]) if (i != par) {
bool go = i == wotDown[cur][0];
int direct = valDown[cur][go] + valDown[cur][1 + (go || i == wotDown[cur][1])];
int indirect = valDiam[cur][i == wotDiam[cur]];
int whoops = valDown[cur][go] + up[cur];
prep(i,cur,max({push,whoops,direct,indirect}));
}
}
void solve (int cur, vector<Edge> &queries) {
int cent = getcent(cur,getsz(cur));
cc = 0; vector<pii> diams, downs;
depth[cent] = 0; done[cent] = 1; case2[cent] = 0;
for (int i : adj[cent]) {
if (!done[i]) {
godown(i,cent); case3[i] = 0;
goup(i,cent,0); diams.emplace_back(subDiam[i],cc); downs.emplace_back(valDown[i][0] + 1, cc);
++cc;
} else {
if (pp[i] == cent) {
diams.emplace_back(subREE[i],-1); downs.emplace_back(down[i] + 1, -1);
} else {
downs.emplace_back(up[cent], -1); diams.emplace_back(upDiam[cent],-1);
}
}
}
sort(diams.rbegin(),diams.rend()); sort(downs.rbegin(),downs.rend());
vector<vector<Edge>> togo(cc);
for (Edge q : queries) {
if (q.a == cent || q.b == cent) {
if (q.a == cent) swap(q.a,q.b);
int direct = 0, cnt = 0, best = 0;
for (pii p : downs) if (p.second != comp[q.a]) {
++cnt; direct += p.first;
if (cnt == 2) break;
best = p.first;
}
int indirect = 0;
for (pii p : diams) if (p.second != comp[q.a]) {
indirect = p.first;
break;
}
int len = max({direct,indirect,case1[q.a]});
int cyc = q.w + depth[q.a];
cnt = n - 1 - depth[q.a];
ret = min(ret,cnt * 2 + cyc - len);
int yeet = q.w + max({case2[q.a]+case2[q.b],depth[q.a]+best+case2[q.b],case2[q.a]+best+depth[q.b]});
ret = min(ret,(n - 2 + q.w) * 2 - yeet);
}
else if (comp[q.a] == comp[q.b]) togo[comp[q.a]].push_back(q);
else {
int direct = 0, cnt = 0, best = 0;
for (pii p : downs) if (p.second != comp[q.a] && p.second != comp[q.b]) {
++cnt; direct += p.first;
if (cnt == 2) break;
best = p.first;
}
int indirect = 0;
for (pii p : diams) if (p.second != comp[q.a] && p.second != comp[q.b]) {
indirect = p.first;
break;
}
int len = max({direct,indirect,case1[q.a],case1[q.b]});
int cyc = q.w + depth[q.a] + depth[q.b];
cnt = n - 1 - depth[q.a] - depth[q.b];
ret = min(ret,cnt * 2 + cyc - len);
int yeet = q.w + max({case2[q.a]+case2[q.b],depth[q.a]+best+case2[q.b],case2[q.a]+best+depth[q.b],case3[q.a]+valDown[q.a][0]+depth[q.b],case3[q.b]+valDown[q.b][0]+depth[q.a]});
ret = min(ret,(n - 2 + q.w) * 2 - yeet);
}
}
int oh = 0;
for (int i : adj[cent]) if (!done[i]) {
solve(i,togo[oh]);
++oh;
}
}
int main () {
int m;
scanf ("%d %d",&n,&m);
vector<Edge> extra;
while (m--) {
int a,b,w;
scanf ("%d %d %d",&a,&b,&w); ++a; ++b;
if (w>1) extra.push_back({a,b,w});
else adj[a].push_back(b), adj[b].push_back(a);
}
ret = solve(1);
godown(1,0); dfs3(1); goup(1);
prep(1); solve(1,extra);
printf ("%d\n",ret);
return 0;
}
