#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = uint64_t;
constexpr int N = 5005, Log = 13;
int n, m;
vector<array<int, 2>> e[N];
ll dis[N], d;
bool vis[N];
ull col[N];
mt19937_64 eng(chrono::steady_clock::now().time_since_epoch().count());
map<uint64_t, ll> sw;
void dfs(int u, int fa) {
	vis[u] = 1;
	for (auto [v, w] : e[u]) {
		if (vis[v]) {
			if (dis[v] < dis[u] && v != fa) {
				ull h = eng();
				col[u] ^= h, col[v] ^= h, sw[h] += w;
				d = __gcd(d, dis[u] - dis[v] + w);
			}
			continue;
		}
		dis[v] = dis[u] + w;
		dfs(v, u);
		sw[col[v]] += w, col[u] ^= col[v];
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i, 0);
		}
	}
	for (auto [x, y] : sw) {
		d = __gcd(d, y * 2);
	}
	cout << d << "\n";
	return 0;
}