#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define coutf cout << fixed << setprecision(10)

#define int long long

struct edge{ // 基本的な辺
    int start, goal;
};

struct direction{ // 辺の終点とコスト
    int goal;
    long cost;
};

struct cost_edge{ // 辺とコスト
    edge e;
    long cost;
};

struct path{ // 辺のコストと辺 最小全域木を求める時に使う
    long cost;
    edge e;
    
    bool operator >(const path& another) const{
        return cost > another.cost;
    }
};

struct influ{ // 「影響」と呼んでいる 頂点0に書かれた値をaとした時、is_plusがtrueなら constant_term + a が、is_plusがfalseなら constant_term - a が書かれる
    long constant_term;
    bool is_plus;
};

void zero(){ // 候補が0であることを出力する関数
    cout << 0 << endl;
    exit(0);
}

signed main(){
    int n, m;
    cin >> n >> m;
    vector<direction> graph[n];
    for(int i = 0; i < m; i++){ // グラフを入力
        int u, v;
        long s;
        cin >> u >> v >> s;
        graph[u - 1].push_back({v - 1, s});
        graph[v - 1].push_back({u - 1, s});
    }
    vector<cost_edge> spanning_tree; // 最小全域木を求める部分
    vector<bool> is_used(n, false);
    is_used[0] = true;
    priority_queue<path, vector<path>, greater<path>> pathes;
    for(auto i: graph[0]){
        pathes.push({i.cost, {0, i.goal}});
    }
    while(!pathes.empty()){
        auto now = pathes.top();
        pathes.pop();
        if(is_used[now.e.goal]){
            continue;
        }
        is_used[now.e.goal] = true;
        spanning_tree.push_back({now.e, now.cost});
        for(auto i: graph[now.e.goal]){
            pathes.push({i.cost, {now.e.goal, i.goal}});
        }
    }
    influ influence[n]; // 影響を求める部分
    influence[0] = {0, true};
    for(int i = 0; i < n - 1; i++){
        influence[spanning_tree[i].e.goal] = {spanning_tree[i].cost - influence[spanning_tree[i].e.start].constant_term, !influence[spanning_tree[i].e.start].is_plus};
    }
    long index_0 = -1; // 各辺に対して影響の和がs_iになっているかを確かめる。正の整数となるaが存在しなければzero()が実行される。 index_0 = 頂点0に書かれる値、未定の場合は-1
    for(int i = 0; i < n; i++){
        for(auto j: graph[i]){
            if((influence[i].is_plus ^ influence[j.goal].is_plus) && influence[i].constant_term + influence[j.goal].constant_term != j.cost){
                zero();
            }else if(influence[i].is_plus && influence[j.goal].is_plus){
                if(j.cost - influence[i].constant_term - influence[j.goal].constant_term <= 0 || (j.cost - influence[i].constant_term - influence[j.goal].constant_term) % 2){
                    zero();
                }else{
                    long a = (j.cost - influence[i].constant_term - influence[j.goal].constant_term) / 2;
                    if(index_0 == -1){
                        index_0 = a;
                    }else if(index_0 != a){
                        zero();
                    }
                }
            }else if(!influence[i].is_plus && !influence[j.goal].is_plus){
                if(influence[i].constant_term + influence[j.goal].constant_term - j.cost <= 0 || (influence[i].constant_term + influence[j.goal].constant_term - j.cost) % 2){
                    cout << 0 << endl;
                    return 0;
                }else{
                    long a = (influence[i].constant_term + influence[j.goal].constant_term - j.cost) / 2;
                    if(index_0 == -1){
                        index_0 = a;
                    }else if(index_0 != a){
                        zero();
                    }
                }
            }
        }
    }
    if(index_0 != -1){
        for(int i = 0; i < n; i++){
            if(influence[i].is_plus){
                if(influence[i].constant_term + index_0 <= 0){
                    zero();
                }
            }else{
                if(influence[i].constant_term - index_0 <= 0){
                    zero();
                }
            }
        }
        cout << 1 << endl;
    }else{
        long left = 0, right = 1e18;
        for(int i = 0; i < n; i++){
            if(influence[i].is_plus){
                left = max(left, -influence[i].constant_term);
            }else{
                right = min(right, influence[i].constant_term);
            }
        }
        cout << max(0l, right - left - 1) << endl;
    }
}


Measured memory_bytes: 15596