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

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

tuple<int,int,ll>e[N],sta[N];
int fa[N],top;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

int n,m;
ll dis[N],dep[N],f[N][25],ans[N];
bool v[N];
void dfs(int x,int fa){
    v[x]=1;
    f[x][0]=fa;
    for(int i=1;i<20;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    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);
    }
}

int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;~i;i--)
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    if(x==y)return x;
    for(int i=19;~i;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}

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

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

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&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);
            // printf("%d %d %lld\n",x,y,z);
        }
    }
    for(int i=1;i<=n;i++)
        if(!v[i])dep[i]=1,dfs(i,0);
    for(int i=1;i<=top;i++){
        auto [x,y,z]=sta[i];
        ans[i]=z+dist(x,y);
    }
    ll tmp=ans[1];
    for(int i=2;i<=top;i++)
        tmp=gcd(tmp,ans[i]);
    printf("%lld\n",tmp);
    return 0;
}