#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];
vector<P>g[N];
struct node{int u,v,w;}e[N<<1];
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};
	dfs(1);for(int i=1;i<=n;i++) if(!v[i]) return cout<<0,0;
	for(int i=1;i<=m;i++)
	{
		auto [u,v,w]=e[i];memset(::v,0,sizeof(::v));(d[u]>d[v])&&(swap(u,v),1);if(fa[v]==u) continue;
		for(int j=v;j^u;j=fa[j]) ::v[j]=1;::v[u]=1;G=__gcd(G,d[v]-d[u]+w);
//		if(n==100)
		{
		for(int j=1;j<=m;j++) if(i^j)
		{
			auto [U,V,W]=e[j];if(!::v[U]&&!::v[V]) 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;
}