#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
int n,m;
const int mx_sz=1000000;
vector <pair<int,int>> a[mx_sz];
int bfs(int t){
    if(t<=0) return 1;
    bool visit[mx_sz];
    for(int i=0;i<n;i++) visit[i]=0;
    visit[0]=1;
    int deq[mx_sz];
    int x[mx_sz];
    bool chet[mx_sz];
    int j1=0;
    int j2=1;
    deq[0]=0;
    x[0]=t;
    chet[0]=0;
    while(j1<j2){
        int ths=deq[j1];
        for(int i=0;i<a[ths].size();i++){
            if(visit[a[ths][i].first]==1) continue;
            visit[a[ths][i].first]=1;
            deq[j2]=a[ths][i].first;
            j2++;
            if(a[ths][i].second-x[ths]<=0){
                if(chet[ths]==0){
                    return -1;
                }
                else{
                    return 1;
                }
            }
            x[a[ths][i].first]=a[ths][i].second-x[ths];
            if(chet[ths]==0){
                chet[a[ths][i].first]=1;
            }
            else{
                chet[a[ths][i].first]=0;
            }
        }
        j1++;
    }
    return 0;
}
int bfs2(int t){
    if(t<=0) return 0;
    bool visit[mx_sz];
    for(int i=0;i<n;i++) visit[i]=0;
    visit[0]=1;
    int deq[mx_sz];
    int x[mx_sz];
    int j1=0;
    int j2=1;
    deq[0]=0;
    x[0]=t;
    while(j1<j2){
        int ths=deq[j1];
        for(int i=0;i<a[ths].size();i++){
            if(visit[a[ths][i].first]==1){
                if(a[ths][i].second!=x[a[ths][i].first]+x[ths]) return 0;
                continue;
            }
            visit[a[ths][i].first]=1;
            deq[j2]=a[ths][i].first;
            j2++;
            if(a[ths][i].second-x[ths]<0) return 0;
            x[a[ths][i].first]=a[ths][i].second-x[ths];
        }
        j1++;
    }
    return 1;
}
int bfs1(){

    bool visit[mx_sz];
    for(int i=0;i<n;i++) visit[i]=0;
    int deq[mx_sz];
    bool chet[mx_sz];
    ll dist1[mx_sz];
    ll dist2[mx_sz];
    int past[mx_sz];
    past[0]=0;
    int past_len[mx_sz];
    past_len[0]=0;
    int j1=0;
    int j2=1;
    bool l=1;
    int g1=0;
    int g2=0;
    visit[0]=1;
    int reb_len=0;
    deq[0]=0;
    dist1[0]=0;
    dist2[0]=0;
    chet[0]=0;
    while(j1<j2){
        int ths=deq[j1];
        for(int i=0;i<a[ths].size();i++){
            if(visit[a[ths][i].first]==1){
                if(chet[a[ths][i].first]==chet[ths]){
                    l=0;
                    g1=ths;
                    g2=a[ths][i].first;
                    reb_len=a[ths][i].second;
                    break;
                }
                else{
                    if(chet[ths]==0){
                        if(dist1[ths]+dist2[a[ths][i].first]!=dist2[ths]+dist1[a[ths][i].first]+a[ths][i].second) return 0;
                    }
                    else{
                        if(dist1[ths]+dist2[a[ths][i].first]+a[ths][i].second!=dist2[ths]+dist1[a[ths][i].first]) return 0;
                    }
                }
                continue;
            }
            visit[a[ths][i].first]=1;
            past[a[ths][i].first]=ths;
            past_len[a[ths][i].first]=a[ths][i].second;
            deq[j2]=a[ths][i].first;
            j2++;
            if(chet[ths]==0){
                chet[a[ths][i].first]=1;
                dist1[a[ths][i].first]=dist1[ths];
                dist2[a[ths][i].first]=dist2[ths];
                dist2[a[ths][i].first]+=a[ths][i].second;
            }
            else{
                chet[a[ths][i].first]=0;
                dist1[a[ths][i].first]=dist1[ths];
                dist2[a[ths][i].first]=dist2[ths];
                dist1[a[ths][i].first]+=a[ths][i].second;
            }
        }
        if(l==0) break;
        j1++;
    }
    if(l==1){
        return -1;
    }
    int y=g1;
    ll sum=reb_len;
    ll sum1=0;
    if(chet[g1]==1)
        sum1=reb_len;
    while(y!=0){
        sum+=past_len[y];
        if(chet[y]==0)
            sum1+=past_len[y];
        y=past[y];
    }
    y=g2;
    while(y!=0){
        sum+=past_len[y];
        if(chet[y]==0)
            sum1+=past_len[y];
        y=past[y];
    }
    //if(sum%2==1) return 0;
    sum/=2;
    return bfs2(sum-sum1);
}
int main() {
	//ios_base::sync_with_stdio(false);
	//cout<<setprecision(20);
	cin>>n>>m;
	for(int i=0;i<m;i++){
	    int u,v,s;
	    cin>>u>>v>>s;
	    u--;
	    v--;
	    a[u].push_back(make_pair(v,s));
	    a[v].push_back(make_pair(u,s));
	}
	int det1=bfs1();
	if(det1>=0){
	    cout<<det1;
	    return 0;
	}
	int mn=-1,mx=1000000001;
	int md=(mn+mx)/2;
	while(mn+1<mx){
        int det=bfs(md);
        if(det>0){
            mn=md;
            md=(mx+md)/2;
        }
        else{
            mx=md;
            md=(mn+md)/2;
        }
    }
    int d1=mn;
    mn=0,mx=1000000001;
    md=(mn+mx)/2;
    while(mn+1<mx){
        int det=bfs(md);
        if(det>=0){
            mn=md;
            md=(mx+md)/2;
        }
        else{
            mx=md;
            md=(mn+md)/2;
        }
    }
    int d2=mn;
    cout<<d2-d1;
}


Measured memory_bytes: 50292