#include <bits/stdc++.h>
using namespace std;
#define M 5005
using ll = long long;
using tl = tuple<int,int,int>;
tl E[M*2];
int n,m;
int f[M];
int find(int p){
    return f[p]==p?p:f[p]=find(f[p]);
}
using pii = pair<int,int>;
vector<pii>edge[M];
bool mark[M];
int fa[M][13],dep[M];
ll dis[M];
void dfs(int F,int now){
    fa[now][0]=F;
    dep[now]=dep[F]+1;
    for(int i=1;i<13;i++)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    for(auto &[to,w]:edge[now])if(to!=F)
        dis[to]=dis[now]+w,dfs(now,to);
}
int LCA(int a,int b){
    if(dep[b]<dep[a])swap(a,b);
    int stp = dep[b]-dep[a];
    for(int i=0;i<13;i++)
        if((1<<i)&stp)b=fa[b][i];
    if(a==b)return a;
    for(int i=12;~i;--i)
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
ll Dis(int a,int b){
    return dis[a]+dis[b] - (dis[LCA(a,b)]<<1);
}
ll solve(){
    for(int i=1;i<=n;i++)edge[i].clear(),f[i]=i;
    for(int i=1;i<=m;i++){
        auto [a,b,w] = E[i];
        mark[i]=0;
        if(find(a)!=find(b)){
            f[find(a)]=find(b);
            edge[a].push_back(pii(b,w));
            edge[b].push_back(pii(a,w));
        }else mark[i]=1;
    }
    dis[1]=0,dfs(0,1);
    ll g = -1;
    for(int i=1;i<=m;i++)if(mark[i]){
        auto [a,b,w] = E[i];
        if(g==-1)g = Dis(a,b) + w;
        else g = __gcd(g,Dis(a,b)+w);
    }
    return g;
}
int main(){
    cin>>n>>m;
    for(int a,b,c,i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        E[i] = tl(a,b,c);
    }
    ll ans = -1;
    for(int i=1;i<=100;i++){
        random_shuffle(E+1,E+1+m);
        ll g = solve();
        if(ans == -1)ans = g;
        else ans = __gcd(ans,g);
    }
    cout<<ans<<endl;
    return 0;
}