#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];

    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) -> void {
            F[x] = max(F[x], D + f[x]);
            for (auto v : G[x]) {
                if (v == fa) continue;
                int nty = (ty || (v != pre[x] && v != nxt[x]));
                self(self, v, x, D + (nty ? -1 : 1), nty);
            }
        };
        dfs3(dfs3, rt);
    }
} p[2];

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);
}

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[a], p[1].F[b]});
    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;
}