#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;
pii back_edges[MAX_M];
int is_anc[MAX_N][MAX_N];
ll ans = 0;

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

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

    solve();
}