#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N=5005, M=1e4+5;

int n,m,bj[M];
struct Edge {int x,y,z;} e[M];

struct edge {int nex,to,v;} a[M<<1];
int h[N],tot=1;
void add(int x,int y,int z)
{
	a[++tot]=(edge){h[x],y,z}, h[x]=tot;
	a[++tot]=(edge){h[y],x,z}, h[y]=tot;
}

int sq[N<<1],in[N],ti; ll dep[N];
void dfs0(int u)
{
	sq[in[u]=++ti]=u;
	for(int i=h[u];i;i=a[i].nex) if(!in[a[i].to])
	{
		bj[i/2]=1;
		int v=a[i].to;
		dep[v]=dep[u]+a[i].v;
		dfs0(v); sq[++ti]=u;
	}
}
#define _min(x,y) (dep[x]<dep[y]?x:y)
int st[N<<1][15],lg[N<<1];
void build_ST()
{
	lg[0]=-1; for(int i=1;i<=ti;++i) st[i][0]=sq[i], lg[i]=lg[i>>1]+1;
	for(int i=1;(1<<i)<=ti;++i)
	for(int l=1;l+(1<<i)-1<=ti;++l)
		st[l][i] = _min(st[l][i-1], st[l+(1<<(i-1))][i-1]);
}
int LCA(int x,int y)
{
	x=in[x], y=in[y];
	if(x>y) swap(x,y);
	int k=lg[y-x+1];
	return _min(st[x][k], st[y-(1<<k)+1][k]);
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1,x,y,z;i<=m;++i)
		scanf("%d %d %d",&x,&y,&z), add(x,y,z), e[i]=(Edge){x,y,z};
	dfs0(1);
	build_ST();
	ll ans=0;
	for(int i=1;i<=m;++i) if(!bj[i])
	{
		int u=e[i].x, v=e[i].y, w=e[i].z;
		if(dep[u]<dep[v]) swap(u,v);
		if(!ans) ans = dep[u]-dep[v]+w;
		else ans = __gcd(ans, dep[u]-dep[v]+w);
		for(int j=i+1;j<=m;++j) if(!bj[j])
		{
			int x=e[j].x, y=e[j].y, z=e[j].z;
			if(dep[x]<dep[y]) swap(x,y);
			
			if(LCA(u,y)==y)
			{
				int dw=LCA(u,x), up=LCA(v,y);
				ans = __gcd(ans, dep[u]-dep[v]+w + dep[x]-dep[y]+z - (dep[dw]-dep[up])*2);
			}
		}
	}
	printf("%lld\n",ans);
}