#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 5e3 + 1;
const int MAX_M = 1e4 + 1;

vector<pii> adj[MAX_N];
vector<int> chd[MAX_N];
bool visited[MAX_N];
int d[MAX_N];
ll h[MAX_N];
int lca[MAX_N][MAX_N];
int be_cnt = 0;
tuple<int, int, ll> back_edges[MAX_M];
bool is_anc[MAX_N][MAX_N];

void dfs(int x) {
    visited[x] = true;
    chd[x].push_back(x);
    for (auto[y, c]: adj[x]) {
        if (!visited[y]) {
            d[y] = d[x]+1;
            h[y] = h[x]+c;
            dfs(y);
            for (int z: chd[y]) chd[x].push_back(z);
        } else if (d[x] < d[y]) {
            back_edges[be_cnt++] = { x, y, h[y]-h[x]+c };
        }
    }
    for (int y: chd[x]) is_anc[y][x] = true;
    for (int y: chd[x]) {
        for (int z: chd[x]) {
            if (!lca[y][z]) lca[y][z] = x;
        }
    }
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    for (int i=1; i<=n; ++i) {
        if (!visited[i]) dfs(i);
    }

    ll ans = 0;
    for (auto[x, y, l]: back_edges) ans = gcd(ans, l);
    for (int i=0; i<be_cnt; ++i) {
        auto[x1, y1, l1] = back_edges[i];
        for (int j=i+1; j<be_cnt; ++j) {
            auto[x2, y2, l2] = back_edges[j];
            int l = lca[y1][y2];
            if (is_anc[x1][x2]) {
                ll inter = h[l] - h[x1];
                if (d[x1] <= d[l]) ans = gcd(ans, l1+l2-inter*2);
            } else if (is_anc[x2][x1]) {
                ll inter = h[l] - h[x2];
                if (d[x2] <= d[l]) ans = gcd(ans, l1+l2-inter*2);
            }
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}