#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];LL d[N],G;bool v[N];
vector<P>g[N],E[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]) E[x].push_back({y,w}),fa[y]=x,d[y]=d[x]+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);::v[u]=::v[v]=0;
		for(int j=1;j<=m;j++)
		{
			auto [U,V,W]=e[j];if(::v[V]) swap(U,V);if(fa[V]==U||fa[U]==V) continue;
			if(::v[U])
			{
				if(::v[V]) G=__gcd(G,(LL)labs(d[U]-d[V])<<1);
				else
				{
					bool ok=1;for(int j=V;j;j=fa[j]) if(j==v){ok=1;break;}
					G=__gcd(G,(LL)(ok?d[v]-d[U]:d[U]-d[u])<<1);
				}
			}
		}
	}
	return cout<<G,0;
}