#include<bits/stdc++.h>

#define maxn 5005
#define INF 1e18
#define pii pair<int,int>
#define int long long

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

struct edge{
	int to;
	int val;
	int next;
}e[2*maxn];

int e_cnt=1,head[maxn];

void add(int u,int v,int w){
	e[e_cnt].to=v;
	e[e_cnt].val=w;
	e[e_cnt].next=head[u];
	head[u]=e_cnt++;
}

int gcd(int a,int b){
	return (b==0)?a:gcd(b,a%b);
}

int n,m,res=0;
vector<pair<pii,int> > E;
int root[maxn];

int f_f(int x){
	if(root[x]!=x){
		root[x]=f_f(root[x]);
	} 
	return root[x];
}

int dfs_cnt=1; 
int f[maxn];
int mapping[maxn],q_map[maxn],depth[maxn],cnt[maxn];
int sz[maxn],son[maxn],rt[maxn];

void dfs1(int x,int fa){
	sz[x]=1;cnt[x]=cnt[fa]+1;
	f[x]=fa;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].to,w=e[i].val;
		if(v==f[x])continue;
		depth[v]=depth[x]+w;
		dfs1(v,x);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]])son[x]=v;
	}
//	cout<<"depth["<<x<<"]="<<depth[x]<<endl; 
}

void dfs2(int x,int RT){
	rt[x]=RT;mapping[dfs_cnt]=x;
	q_map[x]=dfs_cnt++;
	if(son[x])dfs2(son[x],RT);
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].to;
		if(v==son[x]||v==f[x])continue;
		dfs2(v,v);
	}
}

int lca(int u,int v){
	while(rt[u]!=rt[v]){
		if(cnt[rt[u]]<cnt[rt[v]])swap(u,v);
		u=f[rt[u]];
	} 
	if(cnt[u]>cnt[v])return v;
	return u;
}

int dist(int u,int v){
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}

bool on(int u,int v,int x){
	return lca(lca(u,v),x)==lca(u,v)&&(lca(x,u)==x||lca(x,v)==x);
}//x是不是在u,v上 

signed main(){
	
	n=read();m=read();
	for(int i=1;i<=n;i++)root[i]=i;
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read(); 
		if(f_f(a)!=f_f(b)){
			root[f_f(a)]=f_f(b);
			add(a,b,c);add(b,a,c);
		}else{
		//	cout<<"push!"<<endl;
			E.push_back(make_pair(make_pair(a,b),c));
		}
	}
	dfs1(1,0);dfs2(1,1);
	
	for(pair<pair<int,int>,int> p:E){
		res=gcd(res,dist(p.first.first,p.first.second)+p.second);
	}
//	cout<<"res="<<res<<endl;
	
	for(int i=0;i<E.size();++i){
		for(int j=i+1;j<E.size();++j){
			int a=E[i].first.first,b=E[i].first.second,c=E[j].first.first,d=E[j].first.second;
			int l1=dist(a,b)+E[i].second,l2=dist(c,d)+E[j].second;
			int e,w;
			if(on(a,b,lca(c,d))){
				e=lca(c,d);
				if(lca(e,a)==a){
					w=dist(a,e);
				}else{
					w=dist(b,e);
				}
			}else if(on(c,d,lca(a,b))){
				e=lca(a,b);
				if(lca(e,c)==c){
					w=dist(c,e);
				}else{
					w=dist(d,e);
				}
			}
		//	cout<<"l1="<<l1<<" l2="<<l2<<" w="<<w<<endl;
			res=gcd(res,l1);res=gcd(res,l2);
			res=gcd(res,2*w);
		}
	}
	
	printf("%lld\n",res);
	
	return 0;
}