/*input
3 3
1 2 3
2 3 5
1 3 4
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define int long long
#define MAX 100900
#define INF 1e17

struct djs{
    int x[MAX];
    void init(){ REP(i , 0 , MAX) x[i] = i; }
    int Find(int a){ return a == x[a] ? a : x[a] = Find(x[a]); }
    void Union(int a , int b){ x[Find(a)] = Find(b); }
    int operator[](int a){ return Find(a); }
} ds;
vector<PII> v[MAX] , g[MAX];
int n , m , e[MAX][3] , ue[MAX] , dep[MAX] , ans[MAX] , use[MAX];
void DFS(int now , int fa , int deep){
    dep[now] = deep;
    for(auto to : v[now]) if(to.A != fa) DFS(to.A , now , 1 - deep);
}
int giall = 0 , gitwo = 0;
int DFS1(int now , int fa , int wnt , int deep){
    if(now == wnt) return 1;
    int ok = 0;
    for(auto to : v[now]) if(to.A != fa) {
        if(DFS1(to.A , now , wnt , 1 - deep)){
            if(deep == 1) gitwo += to.B;
            giall += to.B;
            ok = 1;
            return 1;
        }
    }
    return 0;
}
void check(int now){
    use[now] = 1;
    for(auto to : g[now]){
        if(use[to.A] == 0){
            ans[to.A] = to.B - ans[now];
            check(to.A);
        }
        else if(ans[now] + ans[to.A] != to.B){
            cout << 0 << endl;
            exit(0);
        }
    }
}
int32_t main(){
    IOS;
    cin >> n >> m;
    REP(i , 1 , m + 1) REP(j , 0 , 3) cin >> e[i][j];

    ds.init();
    REP(i , 1 , m + 1) if(ds[e[i][0]] != ds[e[i][1]]){
        ds.Union(e[i][0] , e[i][1]) , ue[i] = 1;
        v[e[i][0]].pb(e[i][1] , e[i][2]);
        v[e[i][1]].pb(e[i][0] , e[i][2]);
    }
    REP(i , 1 , m + 1){
        g[e[i][0]].pb(e[i][1] , e[i][2]);
        g[e[i][1]].pb(e[i][0] , e[i][2]);
    }

    DFS(1 , 0 , 0);
    REP(i , 1 , m + 1) if(ue[i] == 0 && dep[e[i][0]] % 2 == dep[e[i][1]] % 2){
        // cout << "here" << endl;

        int v1 = e[i][0] , v2 = e[i][1] , val = e[i][2];
        DFS1(v1 , 0 , v2 , 1);
        giall += val;
        // DB4("giall = " , giall , "gitwo = " , gitwo);
        if(giall % 2 == 1) return cout << 0 << endl , 0;
        else ans[v2] = giall / 2 - gitwo;
        check(v2);
        REP(i , 1 , n + 1) if(ans[i] <= 0) return cout << 0 << endl , 0;
        cout << 1 << endl;
        return 0;
    }
    check(1);
    int sml = INF;
    int big = INF;
    REP(i , 1 , n + 1){
        if(dep[i] % 2 == dep[1] % 2){
            sml = min(sml , ans[i]);
        }
        else {
            big = min(big , ans[i]);
        }
    }
    big -= 1 - sml;
    if(big <= 0) cout << 0 << endl;
    else cout << big << endl;
    return 0;
}

Measured memory_bytes: 26368