#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()


struct LCA{
    int N;
    int logn;
    vector<vector<int>> G;
    vector<vector<int>> par;
    vector<int> depth, used;

    LCA(int n) : N(n), logn(0), G(n + 1), depth(n + 1), used(n + 1) {
        while((1 << logn) <= N) logn++;
        par = vector<vector<int>>(logn, vector<int>(n + 1));
    }

    void add_edge(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }

    void dfs(int v, int p, int d){
        par[0][v] = p;
        depth[v] = d;
        used[v] = true;

        for(auto& u : G[v]){
            if(p == u) continue;
            dfs(u, v, d + 1);
        }
    }

    void setting(){
        for (int i = 1; i <= N; i++) {
            if (used[i]) continue;
            dfs(1, -1, 0);
        }
        for(int i = 1; i < logn; i++){
            for(int j = 1; j <= N; j++){
                if(par[i - 1][j] < 0) par[i][j] = -1;
                else par[i][j] = par[i - 1][par[i - 1][j]];
            }
        }
    }

    int get_lca(int u, int v){
        if(depth[u] < depth[v]) swap(u, v);
        int d = depth[u] - depth[v];

        for(int i = 0; i < logn; i++){
            if(d >> i & 1) u = par[i][u];
        }
        if(u == v) return u;

        for(int i = logn - 1; i >= 0; i--){
            if(par[i][u] != par[i][v]){
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }

    int get_len(int u, int v) {
        int cp = get_lca(u, v);
        return depth[u] + depth[v] - depth[cp] * 2;
    }
};

int N, M, par[5010];
ll depth[5010], g;
vector<pil> G[5010];
vector<pil> TG[5010];
vector<pil> rem[5010];
bool used[5010];
LCA lca(0);

void dfs(int v, ll d) {
    used[v] = true;
    depth[v] = d;
    for (auto& [u, w] : G[v]) {
        if (used[u]) {
            if (u != par[v]) {
                rem[v].emplace_back(u, w);
                rem[u].emplace_back(v, w);
            }
            continue;
        }

        par[u] = v;
        TG[v].emplace_back(u, w);
        TG[u].emplace_back(v, w);
        lca.add_edge(u, v);
        dfs(u, d + w);
    }
}

void make_ans(int v, int p) {
    used[v] = true;
    for (auto&& [u, w] : TG[v]) {
        if (u == p) continue;
        make_ans(u, v);
    }

    for (auto&& [u, w] : rem[v]) {
        if (depth[u] > depth[v]) continue;
        g = gcd(g, w + depth[v] - depth[u]);
        int p = v;
        while (true) {
            for (auto&& [q, r] : rem[p]) {
                if (depth[q] < depth[p]) continue;
                if (max(u, v) == max(p, q) && min(u, v) == min(p, q)) continue;
                ll len = w + r + depth[p] - depth[u];
                len += depth[v] + depth[q] - 2 * depth[lca.get_lca(v, q)];
                g = gcd(g, len);
            }

            if (p == u) break;

            p = par[p];

        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> N >> M;
    lca = LCA(N);
    rep (i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }

    rep (i, 1, N + 1) {
        if (used[i]) continue;
        dfs(i, 0);
    }
    lca.setting();
    rep (i, 1, N + 1) used[i] = false;
    rep (i, 1, N + 1) {
        if (used[i]) continue;
        make_ans(i, 0);
    }

    cout << g << endl;
}