#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define i1 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define all(v) v.begin(), v.end()

using namespace std;

template<typename types>
void read(types &x) {
    x = 0; char c = getchar(); int f = 1;
    while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x *= f; return;
}
void read() {}
template<typename types, typename... Args>
void read(types &x, Args&... args) {
    read(x), read(args...);
    return;
}
template<typename types>
void write(types x) {
    if (x < 0) putchar('-'), x = -x;
    types k = x / 10;
    if (k) write(k);
    putchar(x - k * 10 + '0');
    return;
}
void print() { puts(""); }
template<typename types, typename... Args>
void print(types x, Args... args) {
    write(x), putchar(' '), print(args...);
    return;
}

const int MAXN = 1e4 + 10;
const int MAXM = 2e4 + 10;
const int LGN = 20;

int n, m;
struct Edge {
    int x, y, w;
} e[MAXM];
int head[MAXN], to[MAXM], w[MAXM], nxt[MAXM], idx = 1;
ll depth[MAXN], d[MAXN];
int dfn[MAXN], pa[MAXN], rk[MAXN], mn[MAXN][LGN], lg[MAXN], timecnt;

int cmp(int x, int y) { return d[x] < d[y] ? x : y; }
void addedge(int x, int y, int z) {
    nxt[++idx] = head[x];
    to[idx] = y;
    w[idx] = z;
    head[x] = idx;
    return;
}
int query(int l, int r) {
    int k = lg[r - l + 1];
    return cmp(mn[l][k], mn[r - (1 << k) + 1][k]);
}
int lca(int x, int y) {
    if (x == y) return x;
    if (dfn[x] > dfn[y]) swap(x, y);
    return pa[query(dfn[x] + 1, dfn[y])];
}
void dfs(int x) {
    dfn[x] = ++timecnt, rk[dfn[x]] = x;
    mn[rk[x]][0] = x;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        if (!dfn[y]) depth[y] = depth[x] + w[i], d[y] = d[x] + 1, pa[y] = x, dfs(y);
    }
    return;
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main() {
    ios:: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    read(n, m);
    for (int i = 1; i <= m; ++i) {
        int x, y, z; read(x, y, z);
        addedge(x, y, z), addedge(y, x, z);
        e[i].x = x, e[i].y = y, e[i].w = z;
    }
    dfs(1);
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int k = 1; k <= lg[n]; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)
            mn[i][k] = cmp(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]);
    ll g = -1;
    for (int i = 1; i <= m; ++i) {
        if (d[e[i].x] > d[e[i].y]) swap(e[i].x, e[i].y);
        int x = e[i].x, y = e[i].y, w = e[i].w;
        // assert(d[x] < d[y]);
        if (pa[y] == x) continue;
        ll t = depth[y] - depth[x] + w;
        if (~g) g = gcd(g, t);
        else g = t;
    }
    if (g == -1) { print(0); return 0; }
    for (int i = 1; i <= m; ++i) {
        int x1 = e[i].x, y1 = e[i].y;
        assert(d[x1] < d[y1]);
        if (pa[y1] == x1) continue;
        for (int j = i + 1; j <= m; ++j) {
            int x2 = e[j].x, y2 = e[j].y;
            // assert(d[x1] < d[y1] && d[x2] < d[y2]);
            if (pa[y2] == x2) continue;
            int l = lca(y1, y2);
            if (d[x1] < d[x2]) swap(x1, x2);
            int x = x1;
            if (d[x] > d[l]) continue;
            // assert(lca(x, l) == x);
            g = gcd(g, 2 * (depth[l] - depth[x]));
        }
    }
    print(g);
    return 0;
}