#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 5005, Log = 13;
int n, m;
vector<array<int, 2>> e[N];
int dis[N];
vector<array<int, 3>> q;
int col[N], blk, dfc;
int dfn[N], st[N][Log];
bool vis[N];
void dfs(int u, int fa) {
	dfn[u] = ++dfc, st[dfc][0] = fa;
	col[u] = blk;
	vis[u] = 1;
	for (auto [v, w] : e[u]) {
		if (vis[v]) {
			if (v != fa) q.push_back({min(u, v), max(u, v), w});
			continue;
		}
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}
int amin(int u, int v) {
	return dfn[u] < dfn[v] ? u : v;
}
int LCA(int u, int v) {
	if (u == v) return u;
	if (dfn[u] > dfn[v]) swap(u, v);
	int k = __lg(dfn[v] - dfn[u]);
	return amin(st[dfn[u] + 1][k], st[dfn[v] - (1 << k) + 1][k]);
}
int dist(int u, int v) {
	return dis[u] + dis[v] - dis[LCA(u, v)] * 2;
}
int cross(int u1, int v1, int u2, int v2) {
	if (dist(u1, LCA(u2, v2)) + dist(v1, LCA(u2, v2)) != dist(u1, v1)) {
		swap(u1, u2), swap(v1, v2);
	}
	if (dist(u1, LCA(u2, v2)) + dist(v1, LCA(u2, v2)) != dist(u1, v1)) {
		return 0;
	}
	int l = LCA(u2, v2), res = 0;
	if (dist(u1, l) + dist(l, LCA(u1, v1)) == dist(u1, LCA(u1, v1))) {
		res += dis[LCA(u2, u1) ^ LCA(v2, u1) ^ l] - dis[LCA(u1, v1)];
	}
	if (dist(v1, l) + dist(l, LCA(u1, v1)) == dist(v1, LCA(u1, v1))) {
		res += dis[LCA(u2, v1) ^ LCA(v2, v1) ^ l] - dis[LCA(u1, v1)];
	}
	return res;
}
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]) {
			++blk;
			dfs(i, 0);
		}
	}
	for (int j = 1; j < Log; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			st[i][j] = amin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	sort(q.begin(), q.end()), q.erase(unique(q.begin(), q.end()), q.end());
	int d = 0;
	for (auto [u, v, w] : q) {
		d = gcd(d, dist(u, v) + w);
	}
	for (int i = 0; i < q.size(); i++) {
		for (int j = 0; j < i; j++) {
			auto [u1, v1, w1] = q[i];
			auto [u2, v2, w2] = q[j];
			if (col[u1] == col[u2]) {
				d = gcd(d, dist(u1, v1) + w1 + dist(u2, v2) + w2 - cross(u1, v1, u2, v2) * 2);
			}
		}
	}
	cout << d << "\n";
	return 0;
}

answer.code: In function ‘void dfs(long long int, long long int)’:
answer.code:16:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   16 |         for (auto [v, w] : e[u]) {
      |                   ^
answer.code: In function ‘int main()’:
answer.code:75:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   75 |         for (auto [u, v, w] : q) {
      |                   ^
answer.code:76:21: error: ‘gcd’ was not declared in this scope
   76 |                 d = gcd(d, dist(u, v) + w);
      |                     ^~~
answer.code:80:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   80 |                         auto [u1, v1, w1] = q[i];
      |                              ^
answer.code:81:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   81 |                         auto [u2, v2, w2] = q[j];
      |                              ^
answer.code:83:37: error: ‘gcd’ was not declared in this scope
   83 |                                 d = gcd(d, dist(u1, v1) + w1 + dist(u2, v2) + w2 - cross(u1, v1, u2, v2) * 2);
      |                                     ^~~