#include <bits/stdc++.h>

using namespace std;

constexpr int N = 5e5 + 5;

int n, S, T;
vector<int> G[N];
int dep[N];

namespace tree_lca {
    int dfn[N], dfn_c, pos[20][N];
    
    int get(int x, int y) {
        return dfn[x] < dfn[y] ? x : y;
    }

    void init() {
        auto dfs = [&](auto &&self, int x, int fa = 0) -> void {
            dfn[x] = ++dfn_c;
            pos[0][dfn_c] = fa;
            for (auto v : G[x]) {
                if (v != fa) self(self, v, x);
            }
        };
        dfs(dfs, S);
        for (int i = 1; (1 << i) <= n; ++i) {
            for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
                pos[i][j] = get(pos[i - 1][j], pos[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int LCA(int x, int y) {
        if (x == y) return x;
        x = dfn[x], y = dfn[y];
        if (x > y) swap(x, y);
        int k = 31 - __builtin_clz(y - x++);
        return get(pos[k][x], pos[k][y - (1 << k) + 1]);
    }
}

int LCA(int x, int y) {
    return tree_lca::LCA(x, y);
}

vector<int> chain;
int pre[N], nxt[N];

struct Info {
    int f[N], g[N], h[N], F[N], diam[N];

    void init(int rt) {
        auto dfs1 = [&](auto &&self, int x, int fa = 0) -> void {
            for (auto v : G[x]) {
                if (v == fa) continue;
                self(self, v, x);
                if (v != pre[x] && v != nxt[x]) {
                    f[x] = max(f[x], f[v] + 1);
                }
            }
        };
        dfs1(dfs1, rt);
        auto dfs2 = [&](auto &&self, int x, int fa = 0, int D = 1) -> void {
            h[x] = f[x] - D + 1;
            for (auto v : G[x]) {
                if (v != fa && (v == pre[x] || v == nxt[x])) {
                    g[v] = max(g[x], D + f[v]);
                    self(self, v, x, D + 1);
                    h[x] = max(h[x], h[v]);
                }
            }
        };
        dfs2(dfs2, rt);
        auto dfs3 = [&](auto &&self, int x, int fa = 0, int D = 0, int ty = 0, int now = 0) -> void {
            F[x] = max(now, D + f[x]);
            int mx = 0, sec = 0, ind = 0;
            for (auto v : G[x]) {
                if (v == fa || v == pre[x] || v == nxt[x]) continue;
                if (f[v] + 1 > mx) {
                    sec = mx, mx = f[v] + 1, ind = v;
                } else {
                    sec = max(sec, f[v] + 1);
                }
            }
            diam[x] = mx + sec;
            for (auto v : G[x]) {
                if (v == fa) continue;
                int nty = ty + (v != pre[x] && v != nxt[x]), tnow = now;
                if (v != pre[x] && v != nxt[x]) {
                    tnow = max(tnow, D + (v == ind ? mx : mx));
                }
                self(self, v, x, D + (nty == 1 ? 0 : (nty > 1 ? -1 : 1)), nty, tnow);
                if (v != pre[x] && v != nxt[x]) {
                    diam[x] = max(diam[x], diam[v]);
                }
            }
        };
        dfs3(dfs3, rt);
    }
} p[2];

struct Data {
    int mxL, mxR, mx;

    Data operator + (Data y) {
        Data res;
        res.mxL = max(mxL, y.mxL);
        res.mxR = max(mxR, y.mxR);
        res.mx = max({mx, y.mx, mxL + y.mxR});
        return res;
    }
} dt[1 << 20];

void build(int k, int l, int r, vector<Data> &info) {
    if (l == r) {
        dt[k] = info[l - 1];
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid, info);
    build(k << 1 | 1, mid + 1, r, info);
    dt[k] = dt[k << 1] + dt[k << 1 | 1];
}

Data query(int k, int l, int r, int x, int y) {
    if (l >= x && r <= y) return dt[k];
    int mid = (l + r) >> 1;
    if (y <= mid) return query(k << 1, l, mid, x, y);
    if (x > mid) return query(k << 1 | 1, mid + 1, r, x, y);
    return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
}

void init() {
    auto getFar = [&](int st) {
        int mxDep = 0, wh = 0;
        dep[st] = 1;
        auto dfsFar = [&](auto &&self, int x, int fa = 0) -> void {
            for (auto v : G[x]) {
                if (v != fa) dep[v] = dep[x] + 1, self(self, v, x);
            }
            if (dep[x] > mxDep) {
                mxDep = dep[x], wh = x;
            }
        };
        dfsFar(dfsFar, st);
        return wh;
    };
    S = getFar(1), T = getFar(S);
    auto dfsChain = [&](auto &&self, int x) {
        chain.push_back(x);
        if (x == S) return;
        for (auto v : G[x]) {
            if (dep[v] < dep[x]) self(self, v);
        }
    };
    dfsChain(dfsChain, T), reverse(chain.begin(), chain.end());
    for (int i = 1; i < (int)chain.size(); ++i) {
        pre[chain[i]] = chain[i - 1];
        nxt[chain[i - 1]] = chain[i];
    }
    tree_lca::init();
    p[0].init(S), p[1].init(T);
    vector<Data> info;
    for (int i = 0; i < (int)chain.size(); ++i) {
        Data x;
        x.mxL = p[0].f[chain[i]] + 2 * i + 2;
        x.mxR = p[0].f[chain[i]] - 2 * i;
        x.mx = p[0].diam[chain[i]];
        info.push_back(x);
    }
    build(1, 1, dep[T], info);
}

int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}

int query(int x, int y) {
    int a = LCA(x, T), b = LCA(y, T);
    if (dep[a] > dep[b]) swap(x, y), swap(a, b);
    if (dep[a] == dep[b] || dep[a] + 1 == dep[b]) {
        return dep[T] - dep[S];
    }
    int res = dep[T] - dep[S] - (dep[b] - dep[a] - 1) * 2;
    if (a != S) res = max(res, p[0].g[pre[a]]);
    if (b != T) res = max(res, p[1].g[nxt[b]]);
    res = max(res, p[0].h[nxt[a]] + 2 * dep[a]);
    res = max(res, p[1].h[pre[b]] + 2 * (dep[S] + dep[T] - dep[b]));
    res = max({res, p[0].F[x], p[1].F[y]});
    res = max(res, query(1, 1, dep[T], dep[a] + 1, dep[b] - 1).mx);
    return res;
}

signed main() {
    int m; scanf("%d%d", &n, &m);
    vector< array<int, 3> > apd;
    for (int i = 1, x, y, w; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &w), ++x, ++y;
        if (w == 1) G[x].push_back(y), G[y].push_back(x);
        else apd.push_back({x, y, w});
    }
    init();
    int res = 2 * (n - 1) - dis(S, T);
    for (auto [x, y, w] : apd) {
        if (w * 2 <= n) {
            int D = dis(x, y);
            if (D > w) {
                res = min(res, 2 * (n - 1) - D + w - query(x, y));
            }
        }
    }
    printf("%d\n", res);
    return 0;
}