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

vector<pii> adj[MAX_N];
vector<int> chd[MAX_N];
int d[MAX_N];
ll h[MAX_N];
int lca[MAX_N][MAX_N];
int visited[MAX_N];
vector<tuple<int, int, int>> back_edges;
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.push_back({ x, y, 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;
        }
    }
}

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, c]: back_edges) {
        ans = gcd(ans, h[y]-h[x]+c);
    }
    for (int i=0; i<back_edges.size(); ++i) {
        for (int j=i+1; j<back_edges.size(); ++j) {
            auto[x1, y1, c1] = back_edges[i];
            auto[x2, y2, c2] = back_edges[j];
            ll l1 = h[y1]-h[x1]+c1;
            ll l2 = h[y2]-h[x2]+c2;
            int l = lca[y1][y2];
            if (is_anc[x1][x2]) {
                ll inter = h[l] - h[x1];
                ans = gcd(ans, l1 + l2 - inter*2);
            } else if (is_anc[x2][x1]) {
                ll inter = h[l] - h[x2];
                ans = gcd(ans, l1 + l2 - inter*2);
            }
        }
    }
    cout << ans;
}

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

    solve();
}