#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;

const int N = 5e3+23;

vector<pll> g[N];
int h[N], vis[N];
int LCA[N][N];
ll d[N];
vector<pii> be;
vector<int> sub[N];
int n, m;
ll ans=0;

void dfs(int v){
    vis[v]=1;
    sub[v].pb(v);
    LCA[v][v]=v;
    for (auto pp: g[v]){
        int u=pp.F, w=pp.S;
        if(!vis[u]){
            h[u]=h[v]+1;
            d[u]=d[v]+w;
            dfs(u);
            for (int vp: sub[v]) for (int up: sub[u]) LCA[up][vp]=LCA[vp][up]=v;
            for (int up: sub[u]) sub[v].pb(up);
            sub[u].clear();
        }
        else if(h[v]<h[u]){
            be.pb({v, u});
            ans=__gcd(ans, w+d[u]-d[v]);

        }
    }
}

int main()
{

    cin>>n>>m;
    for (int i=0; i<m; i++){
        int v, u, w; cin>>v>>u>>w;
        g[v].pb({u, w}); g[u].pb({v, w});
    }
    for (int v=1; v<=n; v++) if(!vis[v]){
        be.clear();
        dfs(v);
        for (int i=0; i<be.size(); i++) for (int j=i+1; j<be.size(); j++){
            pii a=be[i], b=be[j];
            int v=LCA[a.S][b.S];
            int u=a.F;
            if(d[u]>d[b.F]) u=b.F;
            if(d[v]-d[u]>0) ans=__gcd(ans, 2*(d[v]-d[u]));

        }
    }
    cout<<ans<<endl;
}