#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<random>

const int N = 5e3, M = 1e4;
int n, m, tt, tp, hd[N];
long long d[N], ans;
unsigned long long s[N], t[N];
struct edg { int v, w, nx; bool mk; } e[M];
std::unordered_map<unsigned long long, long long>mp;
std::vector<std::pair<int, int>>g[N];
std::mt19937_64 gen(0xfcc666);
void inline ad(int u, int v, int w) {
	e[tt] = {v, w, hd[u]}, hd[u] = tt++;
}
void dfs(int u) {
	for (int i=hd[u], v, w; ~i; i=e[i].nx)
		if (e[i^1].mk=1, w=d[u]+e[i].w, !e[i].mk)
			if (!~d[v=e[i].v]) d[v] = w, dfs(v),
				mp[s[v]] += e[i].w, s[u] ^= s[v];
			else s[u] ^= t[++tp] = gen(), s[v] ^= t[tp],
				ans = std::__gcd(ans, w-d[v]);
}
int main() {
	std::cin >> n >> m, mp.reserve(n);
	memset(d, -1, n*8), memset(hd, -1, n*4);
	for (int u, v, w; m--;)
		std::cin >> u >> v >> w,
		ad(--u, --v, w), ad(v, u, w);
	for (*d=0, dfs(0); ~tp;) mp[t[tp--]] = 0;
	for (auto[x, y] : mp) ans = std::__gcd(ans, y*2);
	std::cout << ans;
}