#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],f[N<<1][2];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(int i=0;i<h.size();i++)
		{
			auto [u,v,w]=h[i];(d[u]>d[v])&&(swap(u,v),1);basic_string<int>t;
			for(int j=v;j^u;j=fa[j]) t+=j;f[i][0]=t[1];f[i][1]=t.back();
		}
		for(int i=0;i<h.size();i++)
		{
			auto [u,v,w]=h[i];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(int j=0;j<h.size();j++) if(i^j)
			{
				auto [U,V,W]=h[j];if(!vis[U]&&!vis[V]) continue;if(fa[U]==V||fa[V]==U) continue;
				if(!vis[f[j][0]]&&!vis[f[j][1]]) continue;
				if(n==100) cout<<u<<" "<<v<<" "<<U<<" "<<V<<"\n";
				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;
}