#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],W[N];LL d[N],G;bool v[N],vv[N],vis[N];
struct node{int u,v,w;}e[N<<1];
vector<P>g[N];vector<node>h;
void dfs(int x){v[x]=1;for(auto [y,w]:g[x]) if(!v[y]) fa[y]=x,d[y]=d[x]+(W[y]=w),dfs(y);}
int main()
{
	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++) if(v[i]&&!vv[i]) vv[i]=1;h.clear();
		for(int i=1;i<=m;i++) if(vv[e[i].u]) h.push_back(e[i]);
		for(auto [u,v,w]:h)
		{
			memset(vis,0,sizeof(vis));(d[u]>d[v])&&(swap(u,v),1);if(fa[v]==u) continue;
			for(int j=v;j^u;j=fa[j]) vis[j]=1;vis[u]=1;G=__gcd(G,d[v]-d[u]+w);
			for(auto [U,V,W]:h) if(u!=U||v!=V)
			{
				if(!vis[U]&&!vis[V]) continue;if(fa[U]==V||fa[V]==U) continue;
				basic_string<LL>t;t+=d[u];t+=d[v];t+=d[U];t+=d[V];
				sort(t.begin(),t.end());G=__gcd(G,(t[2]-t[1])<<1);
			}
		}	
	}
	
	return cout<<G,0;
}