#include <bits/stdc++.h>

using i64 = int64_t;

i64 gcd(i64 a, i64 b) {
    return b ? gcd(b, a % b) : a;
}

struct DSU {
    std::vector<int> fa;
    explicit DSU(int n) : fa(n) {
        std::iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    int merge(int x, int y) {
        x = find(x), y = find(y);
        fa[x] = y;
    }
};

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

i64 solve(int n, std::vector<std::pair<std::pair<int, int>, int>> edges) {
    std::shuffle(edges.begin(), edges.end(), rng);

    DSU dsu(n);
    std::vector<std::pair<std::pair<int, int>, int>> to_check;
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (auto [p, c] : edges) {
        auto [u, v] = p;
        if (dsu.find(u) != dsu.find(v)) {
            adj[u].emplace_back(v, c);
            adj[v].emplace_back(u, c);
            dsu.merge(u, v);
        } else {
            to_check.emplace_back(p, c);
        }
    }

    // assert(edges.size() - to_check.size() == n - 1);
    std::vector<int> fa(n, -1), size(n), son(n, -1);
    std::vector<i64> dep(n);
    auto dfs1 = [&](auto &self, int node) -> void {
        size[node] = 1;
        for (auto [to, c] : adj[node]) {
            if (to == fa[node]) {
                continue;
            }
            fa[to] = node;
            dep[to] = dep[node] + c;
            self(self, to);
            size[node] += size[to];
            if (size[to] > size[son[node]]) {
                son[node] = to;
            }
        }
    };
    dfs1(dfs1, 0);

    std::vector<int> top(n, -1);
    auto dfs2 = [&](auto &self, int node) -> void {
        if (son[node] != -1) {
            top[son[node]] = top[node];
            self(self, son[node]);
        }
        for (auto [to, c] : adj[node]) {
            if (to == fa[node] || to == son[node]) {
                continue;
            }
            top[to] = to;
            self(self, to);
        }
    };
    top[0] = 0;
    dfs2(dfs2, 0);

    auto lca = [&](int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                std::swap(x, y);
            }
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    };
    auto dist = [&](int x, int y) {
        return dep[x] + dep[y] - dep[lca(x, y)] * 2;
    };

    i64 res = 0;
    for (auto [p, c] : to_check) {
        auto [u, v] = p;
        res = gcd(res, dist(u, v) + c);
    }
    
    return res;
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v, c;
        std::cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    std::vector<uint8_t> vist(n + 1);
    std::vector<int> id(n + 1);
    
    i64 ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (vist[i]) {
            continue;
        }
        std::vector<int> all;
        auto dfs = [&](auto &self, int node) -> void {
            vist[node] = true;
            all.push_back(node);
            for (auto [to, c] : adj[node]) {
                if (!vist[to]) {
                    self(self, to);
                }
            }
        };
        dfs(dfs, i);
        for (int i = 0; i < all.size(); ++i) {
            id[all[i]] = i;
        }

        std::vector<std::pair<std::pair<int, int>, int>> edges;
        for (int i : all) {
            for (auto [to, c] : adj[i]) {
                int u = id[i], v = id[to];
                if (u < v) {
                    edges.push_back(std::make_pair(std::make_pair(u, v), c));
                }
            }
        }

        for (int _ = 0; _ < 1000; ++_) {
            ans = gcd(ans, solve(all.size(), edges));
        }
    }

    std::cout << ans << '\n';
}