#include <bits/stdc++.h>

using namespace std;

mt19937 rng(time(0));

#define int long long

struct rooted_tree {
    struct sparce_table {
        vector<vector<pair<int, int>>> mn;

        sparce_table() {}

        sparce_table(vector<pair<int, int>> &a) {
            build(a);
        }

        void build(vector<pair<int, int>> &a) {
            int n = a.size();
            int logn = __lg(n) + 1;
            mn.assign(logn, vector<pair<int, int>>(n));
            for (int i = 0; i < n; ++i)
                mn[0][i] = a[i];
            for (int l = 0; l < logn - 1; l++)
                for (int i = 0; i + (2 << l) <= n; i++)
                    mn[l + 1][i] = min(mn[l][i], mn[l][i + (1 << l)]);
        }

        pair<int, int> get(int l, int r) {
            if (l > r)
                swap(l, r);
            ++r;
            int t = __lg(r - l);
            return min(mn[t][l], mn[t][r - (1 << t)]);
        }
    };

    vector<int> pos;
    vector<int> dist;
    sparce_table spt;

    rooted_tree(vector<vector<pair<int, int>>> &g) {
        int n = g.size();
        pos.assign(n, -1);
        dist.resize(n);
        vector<pair<int, int>> tr;
        for (int i = 0; i < n; ++i) {
            if (pos[i] == -1)
                dfs(i, g, tr, 0, 0);
        }
        spt.build(tr);
    }

    void dfs(int v, vector<vector<pair<int, int>>> &gr, vector<pair<int, int>> &tr, int depth, int d) {
        pos[v] = tr.size();
        dist[v] = d;
        tr.push_back({depth, v});
        for (auto [u, _]: gr[v])
            if (pos[u] == -1) {
                dfs(u, gr, tr, depth + 1, d + _);
                tr.push_back({depth, v});
            }
    }

    int get(int v, int u) {
        return dist[v] + dist[u] - 2 * dist[spt.get(pos[v], pos[u]).second];
    }

    int lca(int v, int u) {
        return spt.get(pos[v], pos[u]).second;
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    unsigned start = clock();
    
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> gr(n);
    vector<array<int, 3>> e;
    for (int i = 0, u, v, c; i < m; ++i) {
        cin >> u >> v >> c;
        --u, --v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
        e.push_back({u, v, c});
    }
    while ((double)(clock() - start) / CLOCKS_PER_SEC <= 1.9) {
        vector<vector<pair<int, int>>> tree(n);
        vector<bool> used(n, false);
        auto dfs = [&](auto self, int v) -> void {
            shuffle(g[v].begin(), g[v].end(), rng);
            used[v] = true;
            for (auto [u, c]: gr[v]) {
                if (!used[u]) {
                    self(self, u);
                    tree[v].push_back({u, c});
                    tree[u].push_back({v, c});
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            if (!used[i])
                dfs(dfs, i);
        }
        rooted_tree tr(tree);
        int d = 0;
        for (int i = 0; i < m; ++i) {
            if (tr.dist[e[i][0]] > tr.dist[e[i][1]])
                swap(e[i][0], e[i][1]);
            if (tr.dist[e[i][0]] + e[i][2] == tr.dist[e[i][1]])
                continue;
            d = __gcd(d, tr.get(e[i][0], e[i][1]) + e[i][2]);
            for (int j = 0; j < m; ++j) {
                if (tr.dist[e[j][0]] > tr.dist[e[j][1]])
                    swap(e[j][0], e[j][1]);
                if (tr.dist[e[i][0]] > tr.dist[e[j][0]])
                    continue;
                if (tr.dist[e[j][0]] + e[j][2] == tr.dist[e[j][1]])
                    continue;
                if (e[i][0] == e[j][0] && i != j) {
                    d = __gcd(d, tr.get(e[i][1], e[j][1]) + e[i][2] + e[j][2]);
                } else if (i != j) {
                    if (n > 100) {
                        if (tr.dist[e[j][0]] < tr.dist[e[i][1]])
                            d = __gcd(d, tr.get(e[i][0], e[j][0]) + e[i][2] + e[j][2] + tr.get(e[i][1], e[j][1]));
                        else
                            continue;
                    }
                }
            }
        }
    }
    cout << d;
}

answer.code: In lambda function:
answer.code:94:21: error: ‘g’ was not declared in this scope
   94 |             shuffle(g[v].begin(), g[v].end(), rng);
      |                     ^
answer.code: In function ‘int main()’:
answer.code:136:13: error: ‘d’ was not declared in this scope
  136 |     cout << d;
      |             ^