#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e4+10,M=N*2;

int head[N],ver[M],edge[M],nxt[M],tot=1;
void add(int x,int y,ll z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

int n,m;
int dep[N],f[N][25],cnt,dfn[N],Log[N],top,fa[N];
ll dis[N];
tuple<int,int,ll>e[N],sta[N];

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void dfs(int x,int fa){
    dfn[x]=++cnt,f[cnt][0]=x;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        dep[y]=dep[x]+1,dis[y]=dis[x]+edge[i];
        dfs(y,x);
        f[++cnt][0]=x;
    }
}

int cmp(int x,int y){
    if(dep[x]<dep[y])return x;
    else return y;
}

void init(){
    for(int i=1;i<=cnt;i++)Log[i]=log2(i);
    for(int k=1;k<20;k++)
        for(int i=1;i+(1<<k)-1<=cnt;i++)
            f[i][k]=cmp(f[i][k-1],f[i+(1<<(k-1))][k-1]);
}

int LCA(int x,int y){
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int k=Log[y-x+1];
    return cmp(f[x][k],f[y-(1<<k)+1][k]);
}

ll dist(ll x,ll y){
    return dis[x]+dis[y]-2*dis[LCA(x,y)];
}

ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;ll z;
        scanf("%d%d%lld",&x,&y,&z);
        e[i]=make_tuple(x,y,z);
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        auto [x,y,z]=e[i];
        if(find(x)==find(y)){
            sta[++top]=e[i];
        }else{
            fa[find(y)]=find(x);
            add(x,y,z),add(y,x,z);
        }
    }
    if(!top){
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])dfs(i,0);
    init();
    ll ans=-1;
    for(int i=1;i<=top;i++){
        auto [x,y,z]=sta[i];
        ll tmp=dist(x,y)+z;
        if(ans==-1)ans=tmp;
        else ans=gcd(ans,tmp);
    }
    for(int i=1;i<=top;i++)
        for(int j=i+1;j<=top;j++){
            auto [x1,y1,z1]=sta[i];
            auto [x2,y2,z2]=sta[j];
            // printf("<%d %d> <%d %d>\n",x1,y1,x2,y2);
            ll tmp=abs((dist(x1,x2)+dist(y1,y2))-(dist(x1,y2)+dist(x2,y1)));
            ans=gcd(ans,tmp);
        }
    printf("%lld\n",ans);
    return 0;
}