#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=10004;
mt19937_64 rnd(time(0));
bool a1;
ll gcd(ll x,ll y){
    for(ll z;y;x=z){z=y;y=x%y;}
    return x;
}
int n,m,f[N][21],vis[N],dfn[N],par[N],e1[N],e2[N],e3[N],cdfn;
ll ans,dep[N];
ull col[N];
unordered_map<ull,ll>mp;
vector<pair<int,int> >v[N];
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=18;i>=0;--i){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
    }
    if(x==y)return x;
    for(int i=18;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return par[x];
}
void dfs(int x,int p){
    dfn[++cdfn]=x;
    vis[x]=1;
    par[x]=f[x][0]=p;
    for(int i=0;f[x][i];++i)f[x][i+1]=f[f[x][i]][i];
    for(unsigned i=0;i<v[x].size();++i){
        if(vis[v[x][i].fi])continue;
        dep[v[x][i].fi]=dep[x]+v[x][i].se;
        dfs(v[x][i].fi,x);
    }
}
bool a2;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cerr<<"static memory::"<<&a1-&a2<<'\n';
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int &x=e1[i],&y=e2[i],&z=e3[i];
        cin>>x>>y>>z;
        v[x].emplace_back(y,z);
        v[y].emplace_back(x,z);
    }
    dfs(1,0);
    for(int i=1;i<=m;++i){
        int x=e1[i],y=e2[i],z=e3[i];
        if(par[y]!=x&&par[x]!=y){
            ull r=rnd();
            mp[r]+=z;
            col[x]^=r;
            col[y]^=r;
            ans=gcd(ans,dep[x]+dep[y]-2*dep[lca(x,y)]+z);
        }
    }
    for(int i=n;i>=1;--i){
        col[par[dfn[i]]]^=col[dfn[i]];
    }
    for(int i=2;i<=n;++i){
        mp[col[i]]+=dep[i]-dep[par[i]];
    }
    for(auto it=mp.begin();it!=mp.end();++it){
        ans=gcd(ans,2*it->se);
    }
    cout<<ans<<'\n';
    cerr<<"time::"<<clock()<<'\n';
    return 0;
}