#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

#define rep(i, begin, end) for(int i = begin; i < end; i++)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sq(x) (x)*(x)

const int N = 5123;
const int inf = 1e9+7;

vector<array<ll,2>> adj[N];
bool vis[N];
int prof[N];
set<ll> cycle;
int root = 0;
void dfs(int v, int p, ll d){
    vis[v] = 1;
    // cout << "V " << v << " P " << p << " D " << d << '\n'; 
    for(auto [to,c]: adj[v]){
        if(to == p || prof[to] > prof[v]) continue;
        if(to == root){
            // cout << "VERT " << v << " D " << d << " C " << c << " TO " << to << '\n'; 
            cycle.insert(c + d);
        }
        else if(!vis[to]) {prof[to] = prof[v] + 1; dfs(to, v, d + c);}
    }
}

void solvetask()
{
    int n, m;
    cin >> n >> m;

    rep(i,0,m){
        int a,b, c;
        cin >> a >> b >>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    rep(i, 1,n+1){
        memset(vis, 0, sizeof vis);
        memset(prof, 0, sizeof prof);
        // cout << "I " << i << '\n';
        root = i;
        dfs(i, -1, 0);
    }

    if(cycle.empty())
        cout << 0 << '\n';
    else{
        ll mdc = *cycle.begin();
        // cout << "MDC " << mdc << '\n';
        for(auto x: cycle){
            // cout << x << '\n';
            mdc = gcd(mdc, x);}
        
        cout << mdc <<'\n';

    }



}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solvetask();
        // cout << (solvetask() ? "Yes" : "No") << '\n';
}