#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) i&(-i)
const int N = 5e3+5;
int n,m,vis[N],lim[N],on[N*2],dep[N],lca[N][N];
ll cost[N];
int fa[N][15];
struct G{
    ll u,v,w;
}g[N*2];
vector<ll> e[N],path;
void dfs(int u,int eid){
    for(int i=1;i<=12;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
    vis[u] = 1;
    for(int id:e[u]){
        if(id==eid) continue;
        int v=g[id].v,w = g[id].w;
        if(vis[v]) continue;
        fa[v][0] = u,on[id] = 1,dep[v] = dep[u]+1;
        cost[v] = cost[u]+w;
        dfs(v,id);
    }
}
ll dis(int u,int v){
    return cost[u]+cost[v]-2*cost[lca[u][v]];
}
int ask(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int st=lim[u];
    for(int i=st;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u = fa[u][i];
    if(u==v) return u;
    st = lim[v];
    for(int i=st;i>=0;i--) if(fa[u][i]!=fa[v][i]) u = fa[u][i],v = fa[v][i];
    return u; 
}
bool cmp_dep(int x,int y){
    return dep[x]>dep[y];
}
int main(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> g[i].u >> g[i].v >> g[i].w;
        int u=g[i].u,v=g[i].v;
        e[u].pb(i),e[v].pb(i);
    }
    for(int i=1;i<=n;i++) if(!vis[i]) dep[i] = 1,dfs(i,0);
    for(int i=1;i<=n;i++) lim[i] = log2(dep[i])+1;
    for(int i=1;i<=m;i++) if(!on[i]) path.pb(i);
    for(int i=1;i<=n;i++){
        lca[i][i] = i;
        for(int j=i+1;j<=n;j++){
            lca[j][i] = lca[i][j] = ask(i,j);
        }
    }
    ll ans = 0,siz = path.size();
    vector<int> p;
    for(int i=0;i<siz;i++){
        int a=g[path[i]].u,b=g[path[i]].v;
        ll w0 = dis(a,b)+g[path[i]].w;
        if(!ans) ans = w0;
        else ans = __gcd(ans,w0);
        if(m>100) cout << w0 << '\n';
        for(int j=i+1;j<siz;j++){
            int c=g[path[j]].u,d=g[path[j]].v;
            ll w1 = dis(c,d)+g[path[j]].w;
            p.pb(lca[a][c]),p.pb(lca[b][c]);
            p.pb(lca[a][d]),p.pb(lca[b][d]);
            sort(p.begin(),p.end(),cmp_dep);
            if(p[0]!=p[1]) ans = __gcd(ans,w0+w1-2*dis(p[0],p[1]));
            if(m>100 && p[0]!=p[1]) cout << "SP" << w0+w1-2*dis(p[0],p[1]) << '\n';
            p.clear();
        }
    }
    cout << ans;
    return 0;
}