#include <bits/stdc++.h>
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
const int ADD = 1<<19, INF = 1e9;
struct node {
int pv, mv, cv, val;
void init(int x, int d, int d2) {
pv = d + x, mv = d - x, cv = d2;
val = -INF;
}
node operator+(const node &R) const {
node res;
res.pv = max(pv, R.pv);
res.mv = max(mv, R.mv);
res.cv = max(cv, R.cv);
res.val = max({val, R.val, pv + R.mv});
return res;
}
} T[1<<20];
void init(int x, int d, int d2) {
T[ADD+x].init(x, d, d2);
for(int r=(ADD+x)/2;r;r>>=1) {
T[r] = T[r*2] + T[r*2+1];
}
}
int lvt[100], rvt[100];
node read(int l, int r) {
if(l > r) {
node res; res.init(0, -INF, -INF);
return res;
}
l += ADD, r += ADD;
int lt = 0, rt = 0;
while(l <= r) {
if(l & 1) lvt[lt++] = l++;
if(!(r & 1)) rvt[rt++] = r--;
l >>= 1, r >>= 1;
}
while(rt) lvt[lt++] = rvt[--rt];
node res = T[lvt[0]];
for(int i=1;i<lt;i++) res = res + T[lvt[i]];
return res;
}
int N, M;
vector <int> E[500050];
vector <t3> AE;
int dis[500050], pre[500050];
int far(int x) {
memset(dis, -1, sizeof dis);
vector <int> q;
auto ins_q = [&](int x, int d, int p) { if(dis[x] == -1) q.pb(x), dis[x] = d, pre[x] = p; };
ins_q(x, 0, -1);
rep(i, szz(q)) {
int t = q[i];
for(int e : E[t]) ins_q(e, dis[t] + 1, t);
}
return q.back();
}
int fd[500050], dep[500050], up[500050][20], mxd[500050], dv[500050];
vector <pii> chd[500050], dvl[500050];
int get_l(vector <pii> &h, int d, int e = -1) {
int res = 0, rc = 0;
for(auto &[l, y] : h) if(y != e) {
++rc;
res += l;
if(rc == d) return res;
}
return res;
}
int DL[500050][2];
void pdfs(int x) {
for(int e : E[x]) if(fd[e] == -1) {
fd[e] = fd[x];
dep[e] = dep[x] + 1;
up[e][0] = x;
for(int i=1;i<20;i++) up[e][i] = up[ up[e][i-1] ][i-1];
pdfs(e);
mxd[x] = max(mxd[x], mxd[e] + 1);
dv[x] = max(dv[x], dv[e]);
chd[x].pb({mxd[e]+1, e});
dvl[x].pb({dv[e], e});
}
sort(all(chd[x]), greater<>());
sort(all(dvl[x]), greater<>());
dv[x] = max(dv[x], get_l(chd[x], 2, -1));
}
int get_lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
rep(i, 20) if(1<<i & (dep[x] - dep[y])) x = up[x][i];
for(int i=19;i>=0;i--) if(up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
return x == y ? x : up[x][0];
}
int climb(int x, int d) {
rep(i, 20) if(1<<i & d) x = up[x][i];
return x;
}
void qdfs(int x, int u = 0, int h = 0, int fa = -1) {
DL[x][1] = max(dv[x], h);
for(int e : E[x]) if(fd[e] == fd[x] && e != fa) {
int du = 0, dh = max({h, get_l(dvl[x], 1, e), get_l(chd[x], 2, e)});
if(fa != -1) du = max(u, get_l(chd[x], 1, e)) + 1;
DL[e][0] = max(du, mxd[e]);
qdfs(e, du, dh, x);
}
}
int main() {
scanf("%d%d", &N, &M);
rep(i, M) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z); ++x; ++y;
if(z == 1) {
E[x].pb(y);
E[y].pb(x);
}
else AE.pb({x, y, z});
}
int l = far(1);
int r = far(l);
int ans = 2 * (N - 1) - dis[r], lend = dis[r];
vector <int> Dia;
for(int t=r;t!=-1;t=pre[t]) Dia.pb(t);
reverse(all(Dia));
memset(fd, -1, sizeof fd);
rep(i, szz(Dia)) fd[Dia[i]] = i;
for(int e : Dia) pdfs(e);
for(int e : Dia) DL[e][0] = -INF, qdfs(e);
int m = szz(Dia);
rep(i, m) init(i, mxd[Dia[i]], dv[Dia[i]]);
for(auto [x, y, d] : AE) {
if(fd[x] > fd[y]) swap(x, y);
if(fd[x] == fd[y]) {
int lca = get_lca(x, y);
int c = dep[x] + dep[y] - 2 * dep[lca];
ans = min(ans, 2 * N - 2 + d - c - lend);
}
else {
int fx = fd[x], fy = fd[y], rx = Dia[fx], ry = Dia[fy];
node n1 = read(0, fx-1), n2 = read(fx+1, fy-1), n3 = read(fy+1, m-1);
int max_d2 = max({DL[x][1], DL[y][1], n1.pv, n2.cv, n3.mv+(m-1)});
int cx = (dep[x] ? climb(x, dep[x]-1) : -1);
int cy = (dep[y] ? climb(y, dep[y]-1) : -1);
max_d2 = max({max_d2, fx + get_l(chd[rx], 1, cx), m-1-fy + get_l(chd[ry], 1, cy)});
int c = fy - fx + dep[x] + dep[y];
ans = min(ans, 2 * N - 2 + d - c - max_d2);
int max_d1 = max(DL[x][0] + max(fy, m-1-fy) + dep[y], DL[y][0] + max(fx, m-1-fx) + dep[x]);
max_d1 = max(max_d1, fx + dep[x] + (m-1-fy) + dep[y]);
max_d1 = max(max_d1, fx + dep[x] + n2.mv + fy + dep[y]);
max_d1 = max(max_d1, dep[x] + n2.pv - fx + (m-1-fy) + dep[y]);
max_d1 = max(max_d1, n2.val + fy - fx + dep[x] + dep[y]);
ans = min(ans, 2 * N - 4 + d - max_d1);
}
}
printf("%d\n", ans);
return 0;
}
