#include <bits/stdc++.h>
#define EVAL(x) #x " = " << (x)

using std::cin;
using std::cout;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

namespace Random {
    const u32 seed = std::chrono::steady_clock().now().time_since_epoch().count();
    std::mt19937_64 rng{seed};
} // namespace Random

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

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n{}, m{};
    cin >> n >> m;

    std::vector<std::vector<std::tuple<int, int, int>>> links(n);
    for (int i{}; i < m; ++i) {
        int u{}, v{}, w{};
        cin >> u >> v >> w, --u, --v;
        links[u].emplace_back(v, w, i), links[v].emplace_back(u, w, i);
    }

    int tot{};
    i64 ans{};
    std::vector<i64> dis(n);
    std::vector<u64> val(n);
    std::vector<bool> vis(n);
    std::map<u64, i64> sum;

    auto dfs{[&](auto dfs, int u, int w, int from) -> void {
        vis[u] = true;
        for (auto [v, w, id] : links[u]) {
            if (id == from)
                continue;
            if (!vis[v])
                dis[v] = dis[u] + w, dfs(dfs, v, w, id), val[u] ^= val[v];
            else if (dis[v] < dis[u]) {
                u64 x{Random::rng()};
                sum[x] += w, val[u] ^= x, val[v] ^= x;
            }
        }
        if (~from)
            sum[val[u]] += w;
    }};

    for (int i{}; i < n; ++i)
        if (!vis[i])
            dfs(dfs, i, 0, -1);

    for (auto [v, c] : sum)
        if (v)
            ans = gcd(ans, c);
    cout << ans << "\n";
}