#include <bits/stdc++.h>


using namespace std;


#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 edge {
    int to;
    ll w;
    int i;
};


int n, m;
vector<vector<edge>> g;
vector<vector<edge>> rg;
vector<ll> clr;

bool paint(int from, int to, int i, ll mw, ll k) {
    for (auto [toto, w, j] : g[to]) {
        if (toto == from) {
            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) {
            continue;
        }
        if (clr[j] != -1) {
            if (clr[i] != (clr[j] + mw) % k) {
                return false;
            }
            continue;
        }
        clr[j] = (clr[i] + k - (mw % 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;
}

vector<ll> h;


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(){
    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;
}