#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll N = 1e5 + 1;
const ll M = 1e9 + 7;

mt19937_64 rng(static_cast<ll>(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count()));

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

ll n, m;
vector<array<ll, 2>> a[N];
ll vst[N], cnt[N];
array<ll, 2> trace[N];
bool found = 0;
vector<ll> cycle;
ll sum = 0;

void dfs(ll node, ll par) {
    if (found) return;

    vst[node] = 1;
    for (auto [x, w]: a[node]) {
        if (x == par) continue;
        if (vst[x] == 2) continue;
        if (vst[x] == 1) {
            cycle.clear(); found = 1; sum = 0;
            for (array<ll, 2> u = {node, w}; ; u = trace[u[0]]) {
                cycle.push_back(u[0]);
                sum += u[1];
                if (u[0] == x) break;
            }
            // reverse(cycle.begin(), cycle.end());
            // cout << "Debug: " << sum << " : "; for (auto x: cycle) cout << x << ' '; cout << endl;
            break;
        }
        trace[x] = {node, w};
        dfs(x, node);
    }
    vst[node] = 2;
}

void doTest(ll testID) {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        ll u, v, w; cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }

    set<ll> s; for (int i = 1; i <= n; i ++) s.insert(i);

    ll res = 0;
    while (clock() <= 1.95 * CLOCKS_PER_SEC) {
        for (int i = 1; i <= n; i ++)
            if (a[i].size()) random_shuffle(a[i].begin(), a[i].end());

        ll rd = rand(0, s.size() - 1);
        ll node = *(next(s.begin(), rd));

        for (int i = 1; i <= n; i ++) vst[i] = 0;
        found = 0; dfs(node, 0);
        if (!found) s.erase(node);

        ll ores = res;
        res = __gcd(res, sum);
        if (res == ores) cnt[node] ++;
        if (cnt[node] == 100) s.erase(node);
    }
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    // cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(_);
}