#include <bits/stdc++.h>
#define X first
#define Y second
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=10010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n, m;
vector < pii > v[N];
ll dep[N], d;
int par[N][15], deep[N];
vector < pii > luk;
vector < int > smece;

void dfs(int x, int lst) {
	par[x][0] = lst;
	for(int j = 1;j < 15;j++)
		par[x][j] = par[par[x][j - 1]][j - 1];
	cout << x << " " << lst << endl;
	for(pii tmp : v[x]) {
		if(tmp.Y == lst) continue;
		if(dep[tmp.Y] != -1 && dep[tmp.Y] < dep[x]) {
			luk.pb({x, tmp.Y});
			smece.pb(tmp.X);
		} else if(dep[tmp.Y] == -1) {
			dep[tmp.Y] = dep[x] + tmp.X;
			deep[tmp.Y] = deep[x] + 1;
			dfs(tmp.Y, x);
		}
	}
}

int digni(int x, int k){
	for(int j = 0;j < 15;j++)
		if(k & (1 << j)) x = par[x][j];
	return x;
}

int main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dep, -1, sizeof(dep));
	cin >> n >> m;
	for(int i = 0;i < m;i++) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		v[a].pb({c, b});
		v[b].pb({c, a});
	}
	ll d = 0;
	for(int x = 1;x <= n;x++) {
		if(dep[x] != -1) continue;
		dep[x] = 0; dfs(x, x); deep[x] = 0;
		for(int i = 0;i < (int)luk.size();i++) {
		//	cout << " luk " << luk[i].x << " " << luk[i].y << std::endl;
			d = gcd(d, dep[luk[i].x] - dep[luk[i].y] + smece[i]);
			for(int j = 0;j < (int)luk.size();j++) {
				if(i == j) continue;
				if(dep[luk[i].y] > dep[luk[j].y]) continue;
				if(dep[luk[i].x] > dep[luk[j].x]) continue;
				if(dep[luk[j].y] > dep[luk[i].x]) continue;
				if(digni(luk[j].x, deep[luk[j].x] - deep[luk[i].x]) != luk[i].x) continue;
				d = gcd(d, dep[luk[i].x] - dep[luk[j].y]);
			}
		}
		luk.clear(); smece.clear();
	}
	cout << d << endl;
}