#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];
bool visited[MAX_N];
int d[MAX_N];
ll h[MAX_N];
int lca[MAX_N][MAX_N];
vector<pii> back_edges;
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[x]) {
                for (int w: chd[y]) lca[z][w] = x;
            }
            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.push_back({ x, y });
        }
    }
}

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]) {
            back_edges.clear();
            dfs(i);
            for (int i=0; i<back_edges.size(); ++i) {
                for (int j=i+1; j<back_edges.size(); ++j) {
                    auto[x1, y1] = back_edges[i];
                    auto[x2, y2] = back_edges[j];
                    int l = lca[y1][y2];
                    int x = (d[x1] < d[x2] ? x2 : x1);
                    ll inter = h[l] - h[x];
                    if (d[x] <= d[l]) ans = gcd(inter*2, ans);
                }
            }
        }
    }
    cout << ans;
}

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

    solve();
}