#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;
}


int32_t main() {
    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();
    cout << rs << "\n";
    return 0;
}

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


*/