#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid ((l+r)>>1)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define pb push_back

using namespace std;
typedef long long LL;
typedef __int128 i128;
typedef long double ld;
typedef pair <int,int> pii;
const int N=5005;
int n,m,ans;
struct D{int u,v,c;} dat[N<<1];

int getint()
{
	char ch;
	int f=1;
	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x*f;
}

LL getLL()
{
	char ch;
	int f=1;
	while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
	LL x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x*f;
}

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

struct Tree
{
	int n;
	vector <int> fa,f,d,son,siz,top;
	vector <LL> len;
	vector <vector <pii>> vt,res;

	Tree(int _):n(_),fa(n+1),f(n+1),d(n+1),son(n+1),siz(n+1),top(n+1),len(n+1),
				vt(n+1),res(n+1) 
	{
		rep(i,1,n) fa[i]=i;
	}

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

	void addedge(int u,int v,int c)
	{
		if(getfa(u)==getfa(v))
		{
			res[u].pb(make_pair(v,c));
			return;
		}
		vt[u].pb(make_pair(v,c));
		vt[v].pb(make_pair(u,c));
		u=getfa(u);
		v=getfa(v);
		fa[u]=v;
	}

	void dfs1(int x,int fa,int dep)
	{
		d[x]=dep,f[x]=fa,siz[x]=1;
		for(auto i:vt[x])
		{
			int v=i.first;
			if(v==fa) continue;
			len[v]=len[x]+i.second;
			dfs1(v,x,dep+1),siz[x]+=siz[v];
			if(!son[x] || siz[son[x]]<siz[v]) son[x]=v;
		}
	}

	void dfs2(int x,int t)
	{
		top[x]=t;
		if(son[x]) dfs2(son[x],t);
		for(auto i:vt[x])
		{
			int v=i.first;
			if(v==f[x] || v==son[x]) continue;
			dfs2(v,v);
		}
	}

	void init()
	{
		rep(i,1,n) if(fa[i]==i) dfs1(i,0,1),dfs2(i,i);
	}

	int lca(int u,int v)
	{
		while(top[u]!=top[v]) d[top[u]]>d[top[v]]?u=f[top[u]]:v=f[top[v]];
		return d[u]<d[v]?u:v;
	}

	LL dis(int u,int v) {return len[u]+len[v]-2*len[lca(u,v)];}

	LL getans()
	{
		LL ret=0;
		rep(x,1,n) for(auto i:res[x]) 
			ret=gcd(ret,dis(x,i.first)+i.second);
		return ret;
	}
} ;
	
void solve()
{
	n=getint(),m=getint();
	rep(i,1,m) dat[i].u=getint(),dat[i].v=getint(),dat[i].c=getint();
	rep(i,1,n)
	{
		random_shuffle(dat+1,dat+1+m);
		Tree t(n);
		rep(j,1,m) t.addedge(dat[j].u,dat[j].v,dat[j].c);
		t.init();
		ans=gcd(ans,t.getans());
	}
	printf("%lld\n",ans);
}

int main()
{
	int T=1;
	while(T--) solve();
	return 0;
}