#include <bits/stdc++.h>


using namespace std;

#define int long long
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


struct DSU {
    int n;
    vector<int> t;


    void build(int _n) {
        n = _n;
        t.resize(n);
        for (int i = 0; i < n; i += 1) {
            t[i] = i;
        }
    }


    int get(int v) {
        if (t[v] == v) {
            return v;
        }
        return t[v] = get(t[v]);
    }


    void merge(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return;
        }
        t[a] = b;
    }
};

struct edge {
    int to;
    ll w;
    int i;
};


int n, m;
vector<vector<edge>> g;
vector<vector<edge>> rg;
vector<ll> clr;
DSU dsu;
vector<ll> h;
vector<ll> up;


void components_dfs(int v, int p, int pi, int mh) {
    h[v] = mh;
    up[v] = mh;
    for (auto [to, w, i] : g[v]) {
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            if (h[to] < h[v] and pi != -1) {
                dsu.merge(i, pi);
            }
            up[v] = min(up[v], h[to]);
            continue;
        }
        components_dfs(to, v, i, mh + 1);
        up[v] = min(up[v], up[to]);
        if (up[to] < h[v]) {
            if (pi != -1) {
                dsu.merge(i, pi);
            }
        }
    }
}


bool paint(int from, int to, int i, ll mw, ll k) {
    for (auto [toto, w, j] : g[to]) {
        if (toto == from or dsu.get(i) != dsu.get(j)) {
            continue;
        }
        if (clr[j] != -1) {
            if (clr[j] != (clr[i] + w) % k) {
                return false;
            }
            continue;
        }
        clr[j] = (clr[i] + w) % k;
        if (!paint(to, toto, j, w, k)) {
            return false;
        }
    }
    for (auto [fromfrom, w, j] : rg[from]) {
        if (fromfrom == to or dsu.get(i) != dsu.get(j)) {
            continue;
        }
        if (clr[j] != -1) {
            if (clr[i] != (clr[j] + mw) % k) {
                return false;
            }
            continue;
        }
        clr[j] = ((clr[i] - mw) % k + k) % k;
        if (!paint(fromfrom, from, j, w, k)) {
            return false;
        }
    }
    return true;
}


bool check(ll k) {
    clr.assign(m + m, -1);
    for (int from = 0; from < n; from += 1) {
        for (auto [to, w, i] : g[from]) {
            if (clr[i] != -1) {
                continue;
            }
            clr[i] = 0;
            if (!paint(from, to, i, w, k)) {
                return false;
            }
        }
    }
    return true;
}


ll dfs(int v, int p, ll mh) {
    h[v] = mh;
    for (auto [to, w, _] : g[v]) {
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            return h[v] - h[to] + w;
        }
        ll x = dfs(to, v, mh + w);
        if (x != -1) {
            return x;
        }
    }
    return -1;
}

ll find_cycle() {
    h.assign(n, -1);
    for (int v = 0; v < n; v += 1) {
        if (h[v] == -1) {
            ll x = dfs(v, -1, 0);
            if (x != -1) {
                return x;
            }
        }
    }
    return -1;
}



ll solve() {
    dsu.build(2 * m);
    for (int i = 0; i < m; i += 1) {
        dsu.merge(2 * i, 2 * i + 1);
    }
    h.assign(n, -1);
    up.assign(n, -1);
    for (int v = 0; v < n; v += 1) {
        if (h[v] == -1) {
            components_dfs(v, -1, -1, 0);
        }
    }
    ll c = find_cycle();
    if (c == -1) {
        return 0;
    }
    ll val = 1;
    for (ll i = 2; i * i <= c; i += 1) {
        while (c % i == 0) {
            c /= i;
            if (check(val * i)) {
                val *= i;
            }
        }
    }
    if (c > 1) {
        if (check(val * c)) {
            val *= c;
        }
        c = 1;
    }
    return val;
}


void stupid_dfs(int v, int p, ll mask, ll mh, ll& rs) {
    h[v] = mh;
    for (auto [to, w, i] : g[v]) {
        i /= 2;
        if ((mask >> i) % 2 == 0) {
            continue;
        }
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            if (h[to] < h[v]) {
                rs = h[v] - h[to] + w;
            }
            continue;
        }
        stupid_dfs(to, v, mask, mh + w, rs);
    }
}


ll solve_slow() {
    ll rs = 0;
    for (ll mask = 0; mask < (1 << m); mask += 1) {
        h.assign(n, -1);
        for (int v = 0; v < n; v += 1) {
            if (h[v] != -1) {
                continue;
            }
            ll x = -1;
            stupid_dfs(v, -1, mask, 0, x);
            if (x != -1) {
                rs = gcd(rs, x);
            }
        }
    }
    return rs;
}



void random_dfs(int v, int p, ll mh, ll& rs) {
    h[v] = mh;
    shuffle(all(g[v]), rnd);
    for (auto [to, w, i] : g[v]) {
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            if (h[to] < h[v]) {
                rs = gcd(rs, h[v] - h[to] + w);
            }
            continue;
        }
        random_dfs(to, v, mh + w, rs);
    }
}


ll solve_random() {
    ll rs = 0;
    for (int itr = 0; itr < 1000; itr += 1) {
        h.assign(n, -1);
        random_dfs(0, -1, 0, rs);
    }
    return rs;
}

void gen_test(int maxn = 6, int maxm = 8, int maxc = 3) {
    n = rnd() % (maxn - 1) + 2;
    maxm = min(maxm, n * (n - 1) / 2);
    m = rnd() % maxm + 1;
    set<pair<int, int>> st;
    g.assign(n, vector<edge>());
    rg.assign(n, vector<edge>());
    for (int i = 0; i < m; i += 1) {
        int u = rnd() % n;
        int v = rnd() % n;
        while (st.find(make_pair(u, v)) != st.end() || u == v) {
            u = rnd() % n;
            v = rnd() % n;
        }
        st.insert(make_pair(u, v));
        st.insert(make_pair(v, u));
        int c = rnd() % maxc + 1;
        g[u].push_back(edge{ v, c, 2 * i });
        rg[v].push_back(edge{ u, c, 2 * i });
        g[v].push_back(edge{ u, c, 2 * i + 1 });
        rg[u].push_back(edge{ v, c, 2 * i + 1 });
    }
}


void print_test() {
    cout << n << " " << m << "\n";
    for (int v = 0; v < n; v += 1) {
        for (auto [to, w, i] : g[v]) {
            if (i % 2 == 0) {
                cout << v + 1 << " " << to + 1 << " " << w << "\n";
            }
        }
    }
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        gen_test();
        ll right_rs = solve_slow();
        ll my_rs = solve();
        if (right_rs != my_rs) {
            print_test();
            break;
        }
    }
}


int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> m;
    g.assign(n, vector<edge>());
    rg.assign(n, vector<edge>());
    for (int i = 0; i < m; i += 1) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        --u;
        --v;
        g[u].push_back(edge{ v, c, 2 * i });
        rg[v].push_back(edge{ u, c, 2 * i });
        g[v].push_back(edge{ u, c, 2 * i + 1 });
        rg[u].push_back(edge{ v, c, 2 * i + 1 });
    }
    ll rs = solve_random();
    cout << rs << "\n";
    return 0;
}

/*
5 5
1 2 1
1 3 1
1 4 1
2 4 1
4 5 1

*/