#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
#define int long long
struct rooted_tree {
struct sparce_table {
vector<vector<pair<int, int>>> mn;
sparce_table() {}
sparce_table(vector<pair<int, int>> &a) {
build(a);
}
void build(vector<pair<int, int>> &a) {
int n = a.size();
int logn = __lg(n) + 1;
mn.assign(logn, vector<pair<int, int>>(n));
for (int i = 0; i < n; ++i)
mn[0][i] = a[i];
for (int l = 0; l < logn - 1; l++)
for (int i = 0; i + (2 << l) <= n; i++)
mn[l + 1][i] = min(mn[l][i], mn[l][i + (1 << l)]);
}
pair<int, int> get(int l, int r) {
if (l > r)
swap(l, r);
++r;
int t = __lg(r - l);
return min(mn[t][l], mn[t][r - (1 << t)]);
}
};
vector<int> pos;
vector<int> dist;
sparce_table spt;
rooted_tree(vector<vector<pair<int, int>>> &g) {
int n = g.size();
pos.assign(n, -1);
dist.resize(n);
vector<pair<int, int>> tr;
for (int i = 0; i < n; ++i) {
if (pos[i] == -1)
dfs(i, g, tr, 0, 0);
}
spt.build(tr);
}
void dfs(int v, vector<vector<pair<int, int>>> &gr, vector<pair<int, int>> &tr, int depth, int d) {
pos[v] = tr.size();
dist[v] = d;
tr.push_back({depth, v});
for (auto [u, _]: gr[v])
if (pos[u] == -1) {
dfs(u, gr, tr, depth + 1, d + _);
tr.push_back({depth, v});
}
}
int get(int v, int u) {
return dist[v] + dist[u] - 2 * dist[spt.get(pos[v], pos[u]).second];
}
int lca(int v, int u) {
return spt.get(pos[v], pos[u]).second;
}
};
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
unsigned start = clock();
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> gr(n);
vector<array<int, 3>> e;
for (int i = 0, u, v, c; i < m; ++i) {
cin >> u >> v >> c;
--u, --v;
gr[u].push_back({v, c});
gr[v].push_back({u, c});
e.push_back({u, v, c});
}
while ((double)(clock() - start) / CLOCKS_PER_SEC <= 1.9) {
vector<vector<pair<int, int>>> tree(n);
vector<bool> used(n, false);
auto dfs = [&](auto self, int v) -> void {
shuffle(gr[v].begin(), gr[v].end(), rng);
used[v] = true;
for (auto [u, c]: gr[v]) {
if (!used[u]) {
self(self, u);
tree[v].push_back({u, c});
tree[u].push_back({v, c});
}
}
};
for (int i = 0; i < n; ++i) {
if (!used[i])
dfs(dfs, i);
}
rooted_tree tr(tree);
int d = 0;
for (int i = 0; i < m; ++i) {
if (tr.dist[e[i][0]] > tr.dist[e[i][1]])
swap(e[i][0], e[i][1]);
if (tr.dist[e[i][0]] + e[i][2] == tr.dist[e[i][1]])
continue;
d = __gcd(d, tr.get(e[i][0], e[i][1]) + e[i][2]);
for (int j = 0; j < m; ++j) {
if (tr.dist[e[j][0]] > tr.dist[e[j][1]])
swap(e[j][0], e[j][1]);
if (tr.dist[e[i][0]] > tr.dist[e[j][0]])
continue;
if (tr.dist[e[j][0]] + e[j][2] == tr.dist[e[j][1]])
continue;
if (e[i][0] == e[j][0] && i != j) {
d = __gcd(d, tr.get(e[i][1], e[j][1]) + e[i][2] + e[j][2]);
} else if (i != j) {
if (n > 100) {
if (tr.dist[e[j][0]] < tr.dist[e[i][1]])
d = __gcd(d, tr.get(e[i][0], e[j][0]) + e[i][2] + e[j][2] + tr.get(e[i][1], e[j][1]));
else
continue;
}
}
}
}
}
cout << d;
}