#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=5005;
int n,m,fa[N],lca[N][N];LL d[N],G;bool v[N],vv[N];
struct node{int u,v,w;}e[N<<1];
vector<P>g[N];vector<node>h;basic_string<int>son[N];
void dfs(int x)
{
	v[x]=1;
	for(auto [y,w]:g[x]) if(!v[y])
	{
		fa[y]=x,d[y]=d[x]+w,dfs(y);
		for(int i:son[y]) for(int j:son[x]) lca[i][j]=lca[j][i]=x;
		for(int i:son[y]) son[x]+=i;
	}
	for(int i:son[x]) lca[x][i]=lca[i][x]=x;lca[x][x]=x;son[x]+=x;
}
signed main()
{
//	fr(1)
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w}),e[i]={u,v,w};
	for(int k=1;k<=n;k++) if(!v[k])
	{
		memcpy(vv,v,sizeof(v));dfs(k);
		for(int i=1;i<=n;i++) vv[i]^=v[i];h.clear();
		for(int i=1;i<=m;i++) if(vv[e[i].u]) h.push_back(e[i]);
		for(int i=0;i<h.size();i++)
		{
			auto [u,v,w]=h[i];(d[u]>d[v])&&(swap(u,v),1);if(fa[v]==u) continue;
			G=__gcd(G,d[v]-d[u]+w);
			for(int j=0;j<h.size();j++) if(i^j)
			{
				auto [U,V,W]=h[j];(d[U]>d[V])&&(swap(U,V),1);V=lca[v][V];
				int up=(d[u]>d[U])?u:U;if(fa[V]==U||d[up]>=d[V]) continue;
				G=__gcd(G,(d[V]-d[up])<<1);
			}
		}
//		if(n==5000&&m==9997) cout<<"*";
	}
	
	return cout<<G,0;
}