Problem:
 Score : 600 points    Problem Statement Kenkoooo found a simple connected graph.
The vertices are numbered 1 through n .
The i -th edge connects Vertex u_i and v_i , and has a fixed integer s_i .  Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:   For every edge i , the sum of the positive integers written in Vertex u_i and v_i is equal to s_i .   Find the number of such ways to write positive integers in the vertices.      Constraints  2 \leq n \leq 10^5  1 \leq m \leq 10^5  1 \leq u_i < v_i \leq n  2 \leq s_i \leq 10^9  If i\neq j , then u_i \neq u_j or v_i \neq v_j .  The graph is connected.  All values in input are integers.         Input Input is given from Standard Input in the following format:  n  m  u_1  v_1  s_1  :  u_m  v_m  s_m       Output Print the number of ways to write positive integers in the vertices so that the condition is satisfied.        Sample Input 1 3 3
1 2 3
2 3 5
1 3 4      Sample Output 1 1  The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3 , respectively.
There is no other way to satisfy the condition, so the answer is 1 .       Sample Input 2 4 3
1 2 6
2 3 7
3 4 5      Sample Output 2 3  Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4 , respectively.
There are three quadruples (a,b,c,d) that satisfy the condition:   (a,b,c,d)=(1,5,2,3)  (a,b,c,d)=(2,4,3,2)  (a,b,c,d)=(3,3,4,1)        Sample Input 3 8 7
1 2 1000000000
2 3 2
3 4 1000000000
4 5 2
5 6 1000000000
6 7 2
7 8 1000000000      Sample Output 3 0

Solution (Python):

from collections import deque
N,M=map(int,input().split())
G=[{} for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    u-=1;v-=1
    G[u][v]=s;G[v][u]=s
H=[(0,0) for i in range(N)]
t=None
q=deque([0])
H[0]=(1,0)
while(q):
    r=q.pop()
    for p in G[r]:
        s=G[r][p]
        tmp=(-H[r][0],s-H[r][1])
        if H[p]==(0,0):
            H[p]=tmp
            q.append(p)
        elif H[p]==tmp:
            pass
        else:
            if H[p][0]==tmp[0]:
                print(0)
                exit()
            else:
                a=H[p][1]
                b=tmp[1]
                if H[p][0]==-1:
                    a,b=b,a
                
                
                if (b-a)%2:
                    print(0)
                    exit()
                else:
                    t=(b-a)//2
'''
t+a>=0:t>=-a
-t+b>=0:t<=b
inf=max(a)
sup=min(b)
'''
if t==None:
    inf=0
    sup=10**18
    for i in range(N):
        if H[i][0]==1:
            inf=max(inf,-H[i][1])
        else:
            sup=min(sup,H[i][1])
    print(max(sup-inf-1,0))
else:
    ans=[None for i in range(N)]
    q=deque([0])
    ans[0]=t
    while(q):
        r=q.pop()
        for p in G[r]:
            if ans[p]==None:
                ans[p]=G[r][p]-ans[r]
                q.append(p)
    flag=1
    for i in range(N):
        for j in G[i]:
            if ans[i]+ans[j]!=G[i][j]:
                flag=0
                break
        if flag==0:
            break
    if flag and min(ans)>0:
        print(1)
    else:
        print(0)

Solution (Python):
















from collections import defaultdict, deque


def main():
    INF = 10 ** 15
    N, M = map(int, input().split())
    S = defaultdict(int)
    adj = defaultdict(list)
    for _ in range(M):
        u, v, s = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
        S[(u, v)], S[(v, u)] = s, s
    even_sum_s, odd_sum_s = [- INF] * N, [INF] * N
    start = 0
    even_sum_s[start] = 0
    que = deque([(start, -1, 0, 0)])  
    unique_n = -1
    
    while len(que) > 0:
        node, parent_node, dist, sum_s = que.pop()
        for next_node in adj[node]:
            if parent_node == next_node:
                continue
            next_dist = dist + 1
            if next_dist % 2 == 1:
                next_sum_s = sum_s + S[(node, next_node)]
                if even_sum_s[next_node] != - INF:
                    s = next_sum_s + even_sum_s[next_node]
                    if s < 2 or s % 2 != 0 or (unique_n > 0 and unique_n != s // 2):
                        print(0)
                        return
                    unique_n = s // 2
                if odd_sum_s[next_node] == INF:
                    odd_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if odd_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
            else:
                next_sum_s = sum_s - S[(node, next_node)]
                if odd_sum_s[next_node] != INF:
                    s = odd_sum_s[next_node] + next_sum_s
                    if s < 2 or s % 2 != 0 or (unique_n > 0 and unique_n != s // 2):
                        print(0)
                        return
                    unique_n = s // 2
                if even_sum_s[next_node] == - INF:
                    even_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if even_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
    lower, upper = max(even_sum_s), min(odd_sum_s)
    if unique_n > 0:
        if lower < unique_n < upper:
            print(1)
        else:
            print(0)
    else:
        print(max(0, upper - lower - 1))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        u,v,s=MI()
        u-=1
        v-=1
        adj[u].append((v,s))
        adj[v].append((u,s))
    
    
    
    
    X=[0]*N
    C=[0]*N
    
    X[0]=1
    
    floor=1
    ceil=10**9
    
    import queue
    q=queue.Queue()
    q.put((0,-1))
    
    while not q.empty():
        v,p=q.get()
        
        
        for nv,s in adj[v]:
            if nv!=p:
                nx=X[v]*(-1)
                nc=s-C[v]
                
                
                if X[nv]==0 and C[nv]==0:
                    q.put((nv,v))
                    X[nv]=nx
                    C[nv]=nc
                    
                    
                    if nx==1:
                        floor=max(floor,-1*nc+1)
                        
                    
                    else:
                        ceil=min(ceil,nc-1)
                        
                else:
                    
                    if nx==X[nv] and nc==C[nv]:
                        pass
                    
                    elif nx==X[nv]:
                        ceil=-1
                    
                    else:
                        ac=0
                        bc=0
                        if nx==1:
                            ac=nc
                            bc=C[nv]
                        else:
                            ac=C[nv]
                            bc=nc
                        
                        
                        aa=bc-ac
                        
                        if aa<=0 or aa%2==1:
                            ceil=-1
                        else:
                            ceil=ceil=min(ceil,aa//2)
                            floor=max(floor,aa//2)
                
                            
    ans=ceil-floor+1
    if ans<=0:
        ans=0
    print(ans)
    
    
                            

                        
    

main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
if x != -1:
    if mi <= x <= ma:
        print(1)
    else:
        print(0)
else:
    print(max(ma - mi + 1, 0))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int, readline().split())
uvs = list(map(int,read().split()))

links = [dict() for _ in range(n+1)]
it = iter(uvs)
for u,v,s in zip(it,it,it):
    links[u][v] = s
    links[v][u] = s

def dfs(root, init):
    nums = [0] * (n+1)
    depth = [-1] * (n+1)
    parent = [-1] * (n+1)

    nums[root] = init
    depth[root] = 0
    stack = [root]
    while(stack):
        next = []
        while(stack):
            i = stack.pop()
            for j,s_ij in links[i].items():
                if(j == parent[i]):
                    continue

                num_j = s_ij - nums[i]
                if(depth[j] != -1)&(nums[j] != num_j):
                    loop_len = depth[j] + depth[i] + 1
                    if(loop_len%2 == 0):
                        print(0)
                        exit()
                    else:
                        num_j = nums[j] + num_j
                        if(num_j % 2 ==1):
                            print(0)
                            exit()
                        return (False, nums,depth,j,num_j//2)
                elif(depth[j] == -1):
                    depth[j] = depth[i] + 1
                    nums[j] = num_j
                    parent[j] = i
                    next.append(j)
        stack = next[::]

    return(True, nums,depth,0,0)

flag,nums,depth,root,init = dfs(1,0)

if(flag==False):
    flag2,nums,depth,root,init = dfs(root,init)
    if(flag2==False):
        print(0)
    else:
        if(min(nums[1:]) < 1):
            print(0)
        else:
            print(1)
    exit()

even = []
odd = []
for i in range(1,n+1):
    if(depth[i]%2==0):
        even.append(nums[i])
    else:
        odd.append(nums[i])

min0 = min(even)
min1 = min(odd)

ans = 1 + (min0-1) + (min1-1)
print(max(0,ans))

Solution (Python):
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    g = False
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,s = map(int,ipt().split())
        way[u].append((v,s))
        way[v].append((u,s))
    ans = [10**18]*(n+1)
    par = [0]*(n+1)
    ans[1] = 1
    q = [1]
    par[1] = 1
    while q:
        qi = q.pop()
        pqi = par[qi]
        aqi = ans[qi]
        for i,si in way[qi]:
            if ans[i] == 10**18:
                q.append(i)
                ans[i] = si-aqi
                par[i] = pqi*(-1)
            elif par[i] == pqi:
                g = True
                a = ans[i]+si-aqi
                if a&1:
                    print(0)
                    exit()
                stt = i
                sa = a//2
                if sa <= 0:
                    print(0)
                    exit()
                break
            elif ans[i] != si-aqi:
                print(0)
                exit()
        if g:
            break
    if g:
        ans = [10**18]*(n+1)
        ans[stt] = sa
        q = [stt]
        while q:
            qi = q.pop()
            aqi = ans[qi]
            for i,si in way[qi]:
                if ans[i] == 10**18:
                    if si-aqi <= 0:
                        print(0)
                        exit()
                    q.append(i)
                    ans[i] = si-aqi
                elif ans[i] != si-aqi:
                    print(0)
                    exit()
        print(1)
    else:
        p1 = []
        m1 = []
        for i in range(1,n+1):
            if par[i] == 1:
                p1.append(ans[i])
            else:
                m1.append(ans[i])
        print(max(0,min(m1)+min(p1)-1))



    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
def bipar(graph,n,m):
  ls = [0]*(n+1)
  stack = [1]
  ls[1] = 1
  while stack:
    x = stack.pop()
    for y,_ in graph[x]:
      if ls[y] == 0:
        ls[y] = 3-ls[x]
        stack.append(y)
      elif ls[y] == ls[x]:
        return False
  return ls
color = bipar(graph,n,m)
if color != False:
  num = [10**18]*(n+1)
  num[1] = 0
  stack = [1]
  mn1 = 10**18
  mn2 = 10**18
  while stack:
    x = stack.pop()
    if color[x] == 1:
      mn1 = min(mn1,num[x])
    else:
      mn2 = min(mn2,num[x])
    for y,d in graph[x]:
      if num[y] == 10**18:
        num[y] = d-num[x]
        stack.append(y)
      elif num[x]+num[y] != d:
        print(0)
        exit()
  print(max(0,mn1+mn2-1))
else:
  num = [10**18]*(n+1)
  num[1] = 1
  stack = [1]
  flg = 0
  while stack:
    x = stack.pop()
    for y,d in graph[x]:
      if num[y] == 10**18:
        num[y] = d-num[x]
        stack.append(y)
      elif num[x]+num[y] != d:
        if not flg:
          s = num[x]
          t = num[y]
          z = (s+t-d)//2
          num = [10**18]*(n+1)
          stack = [x,y]
          num[x] = s-z
          num[y] = t-z
          while stack:
            x = stack.pop()
            for y,d in graph[x]:
              if num[y] == 10**18:
                num[y] = d-num[x]
                stack.append(y)
              elif num[x]+num[y] != d:
                print(0)
                exit()
          if min(num) > 0:
            print(1)
            exit()
        else:
          print(0)
          exit()
  if min(num) > 0:
    print(1)
  else:
    print(0)

Solution (Python):
import sys

input=sys.stdin.readline

n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    u,v,s=map(int,input().split())
    edge[u-1].append((v-1,s))
    edge[v-1].append((u-1,s))

ans=[1 for i in range(n)]
pm=[True]*n

used=[False]*n
used[0]=True

que=[0]
while que:
    u=que.pop()
    for v,s in edge[u]:
        if not used[v]:
            pm[v]=(not pm[u])
            ans[v]=s-ans[u]
            used[v]=True
            que.append(v)

flag=True
bipart=True
for u in range(n):
    for v,s in edge[u]:
        if ans[u]+ans[v]!=s:
            flag=False
        if pm[u]==pm[v]:
            bipart=False
            check=(u,v,s)

if bipart:
    upper=float("inf")
    lower=1

    for v in range(1,n):
        if pm[v]:
            lower=max(lower,2-ans[v])
        else:
            upper=min(upper,ans[v])

    if flag:
        if upper<lower:
            print(0)
        else:
            print(upper-lower+1)
    else:
        print(0)
else:
    u,v,s=check
    a,b=ans[u],ans[v]
    if pm[u]:
        diff=s-(ans[u]+ans[v])
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

    else:
        diff=(ans[u]+ans[v])-s
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

Solution (Python):
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    u,v,s=map(int,input().split())
    edge[u-1].append((v-1,s))
    edge[v-1].append((u-1,s))

ans=[1 for i in range(n)]
pm=[True]*n

used=[False]*n
used[0]=True

que=[0]
while que:
    u=que.pop()
    for v,s in edge[u]:
        if not used[v]:
            pm[v]=(not pm[u])
            ans[v]=s-ans[u]
            used[v]=True
            que.append(v)

flag=True
bipart=True
for u in range(n):
    for v,s in edge[u]:
        if ans[u]+ans[v]!=s:
            flag=False
        if pm[u]==pm[v]:
            bipart=False
            check=(u,v,s)

if bipart:
    upper=float("inf")
    lower=1

    for v in range(1,n):
        if pm[v]:
            lower=max(lower,2-ans[v])
        else:
            upper=min(upper,ans[v])

    if flag:
        if upper<lower:
            print(0)
        else:
            print(upper-lower+1)
    else:
        print(0)
else:
    u,v,s=check
    a,b=ans[u],ans[v]
    if pm[u]:
        diff=s-(ans[u]+ans[v])
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

    else:
        diff=(ans[u]+ans[v])-s
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

def bfs():
    q = deque([0])
    dist = [-1]*n
    dist[0] = 0
    a = [-1]*n
    a[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                a[nv] = w-a[v]
                q.append(nv)
    
    return dist, a
                
n, m = map(int, input().split())
G = [[] for _ in range(n)]
edges = []

for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
    edges.append((u-1, v-1, s))

dist, a = bfs()
ts = set()

for u, v, s in edges:
    if dist[u]%2!=dist[v]%2:
        if a[u]+a[v]!=s:
            print(0)
            exit()
    else:
        if dist[u]%2==0:
            if s-a[u]-a[v]>=2 and (s-a[u]-a[v])%2==0:
                ts.add((s-a[u]-a[v])//2)
            else:
                print(0)
                exit()
        else:
            if a[u]+a[v]-s>=2 and (a[u]+a[v]-s)%2==0:
                ts.add((a[u]+a[v]-s)//2)
            else:
                print(0)
                exit()

if len(ts)>=2:
    print(0)
    exit()

l = 1
r = 10**18
    
for i in range(n):
    if dist[i]%2==0:
        l = max(l, -a[i]+1)
    else:
        r = min(r, a[i]-1)

if len(ts)==1:
    if l<=list(ts)[0]<=r:
        print(1)
    else:
        print(0)
else:
    print(max(0, r-l+1))

Solution (Python):
def main():
    
    n, m = map(int, input().split())
    uvs = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in uvs]
    [g[b-1].append([a-1, c]) for a, b, c in uvs]

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    g2 = [{(j, k) for j, k in gg} for gg in g]  
    q = [0]  
    q_dict = {0: 0}  
    ac_even = [0]  
    ac_odd = [0]  
    flag = False  
    while q:
        i = q[-1]
        
        if g2[i]:
            j, k = g2[i].pop()
            g2[j].remove((i, k))
            
            if j in q_dict:
                l = q_dict[j]
                loop_size = len(q)-l
                if len(q) % 2 == 1:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
                
                if loop_size % 2 == 0:
                    
                    if ac_even[-1]-ac_even[-loop_size//2-1] != ac_odd[-1]-ac_odd[-loop_size//2-1]:
                        print(0)
                        return
                    if len(q) % 2 == 1:
                        ac_even.pop()
                    else:
                        ac_odd.pop()
                
                else:
                    flag = True
                    if len(q) % 2 == 1:
                        s = ac_even[-1]-ac_even[-loop_size//2-1] - \
                            ac_odd[-1]+ac_odd[-loop_size//2]
                    else:
                        s = ac_odd[-1]-ac_odd[-loop_size//2-1] - \
                            ac_even[-1]+ac_even[-loop_size//2]
                    if s <= 0 or s % 2 != 0:
                        print(0)
                        return
                    else:
                        ini = [j, s//2]
                        break
            
            else:
                q_dict[j] = len(q)
                q.append(j)
                if len(q) % 2 == 0:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
        
        else:
            if len(q) % 2 == 0:
                ac_even.pop()
            else:
                ac_odd.pop()
            q.pop()
            q_dict.pop(i)

    
    
    
    g2 = [{(j, k) for j, k in gg} for gg in g]  
    if flag:
        i, j = ini
        visited = [-1]*n
        visited[i] = j
        q = [i]
        while q:
            i = q[-1]
            j = visited[i]
            if g2[i]:
                k, l = g2[i].pop()
                q.append(k)
                g2[k].remove((i, l))
                new = l-j
                if new <= 0:
                    print(0)
                    return
                if visited[k] == -1:
                    visited[k] = new
                elif visited[k] != new:
                    print(0)
                    return
            else:
                q.pop()
        print(1)
    
    
    
    
    
    else:
        visited = [None]*n
        visited[0] = [1, 10**9]
        q = [0]
        s = []
        while q:
            i = q[-1]
            m, M = visited[i]
            if g2[i]:
                j, k = g2[i].pop()
                q.append(j)
                s.append(k)
                g2[j].remove((i, k))
                newM = max(k-m, 0)
                newm = max(k-M, 1)
                if newM == 0:
                    print(0)
                    return
                if visited[j] != None:
                    newM = min(newM, visited[j][1])
                    newm = max(newm, visited[j][0])
                    if newm > newM:
                        print(0)
                        return
                visited[j] = [newm, newM]
            else:
                q.pop()
                if q:
                    j = q[-1]
                    k = s.pop()
                    m, M = visited[i]
                    newM = max(k-m, 0)
                    newm = max(k-M, 1)
                    if newM == 0:
                        print(0)
                        return
                    if visited[j] != None:
                        newM = min(newM, visited[j][1])
                        newm = max(newm, visited[j][0])
                        if newm > newM:
                            print(0)
                            return
                    visited[j] = [newm, newM]
        print(visited[0][1]-visited[0][0]+1)


main()

Solution (Python):
def main():
    
    n, m = map(int, input().split())
    uvs = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in uvs]
    [g[b-1].append([a-1, c]) for a, b, c in uvs]

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    g2 = [{(j, k) for j, k in gg} for gg in g]  
    q = [0]  
    q_dict = {0: 0}  
    ac_even = [0]  
    ac_odd = [0]  
    flag = False  
    while q:
        i = q[-1]
        
        if g2[i]:
            j, k = g2[i].pop()
            g2[j].remove((i, k))
            
            if j in q_dict:
                l = q_dict[j]
                loop_size = len(q)-l
                if len(q) % 2 == 1:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
                
                if loop_size % 2 == 0:
                    
                    if ac_even[-1]-ac_even[-loop_size//2-1] != ac_odd[-1]-ac_odd[-loop_size//2-1]:
                        print(0)
                        return
                    if len(q) % 2 == 1:
                        ac_even.pop()
                    else:
                        ac_odd.pop()
                
                else:
                    flag = True
                    if len(q) % 2 == 1:
                        s = ac_even[-1]-ac_even[-loop_size//2-1] - \
                            ac_odd[-1]+ac_odd[-loop_size//2]
                    else:
                        s = ac_odd[-1]-ac_odd[-loop_size//2-1] - \
                            ac_even[-1]+ac_even[-loop_size//2]
                    if s <= 0 or s % 2 != 0:
                        print(0)
                        return
                    else:
                        ini = [j, s//2]
                        break
            
            else:
                q_dict[j] = len(q)
                q.append(j)
                if len(q) % 2 == 0:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
        
        else:
            if len(q) % 2 == 0:
                ac_even.pop()
            else:
                ac_odd.pop()
            q.pop()
            q_dict.pop(i)

    
    
    
    g2 = [{(j, k) for j, k in gg} for gg in g]  
    if flag:
        i, j = ini
        visited = [-1]*n
        visited[i] = j
        q = [i]
        while q:
            i = q[-1]
            j = visited[i]
            if g2[i]:
                k, l = g2[i].pop()
                q.append(k)
                g2[k].remove((i, l))
                new = l-j
                if new <= 0:
                    print(0)
                    return
                if visited[k] == -1:
                    visited[k] = new
                elif visited[k] != new:
                    print(0)
                    return
            else:
                q.pop()
        print(1)
    
    
    
    
    
    else:
        visited = [None]*n
        visited[0] = [1, 10**9]
        q = [0]
        s = []
        while q:
            i = q[-1]
            m, M = visited[i]
            if g2[i]:
                j, k = g2[i].pop()
                q.append(j)
                s.append(k)
                g2[j].remove((i, k))
                newM = max(k-m, 0)
                newm = max(k-M, 1)
                if newM == 0:
                    print(0)
                    return
                if visited[j] != None:
                    newM = min(newM, visited[j][1])
                    newm = max(newm, visited[j][0])
                    if newm > newM:
                        print(0)
                        return
                visited[j] = [newm, newM]
            else:
                q.pop()
                if q:
                    j = q[-1]
                    k = s.pop()
                    m, M = visited[i]
                    newM = max(k-m, 0)
                    newm = max(k-M, 1)
                    if newM == 0:
                        print(0)
                        return
                    if visited[j] != None:
                        newM = min(newM, visited[j][1])
                        newm = max(newm, visited[j][0])
                        if newm > newM:
                            print(0)
                            return
                    visited[j] = [newm, newM]
        print(visited[0][1]-visited[0][0]+1)


main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))

s = [1]
colour = [0] * (N + 1)
colour[1] = 1
bipartite = 1
while len(s):
  x = s.pop()
  for y, _ in e[x]:
    if colour[y]:
      if colour[y] == colour[x]: bipartite = 0
      continue
    colour[y] = colour[x] % 2 + 1
    s.append(y)

inf = 10 ** 10

def check(x):
  nums = [inf] * (N + 1)
  nums[1] = x
  s = [1]
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
      elif nums[y] != c - nums[x]:
        return False
  if min(nums) > 0: return True
  else: return False

if bipartite:
  nums = [inf] * (N + 1)
  nums[1] = 1
  s = [1]
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
  d = 0
  for x in range(2, N + 1):
    if nums[x] > 0: continue
    if colour[x] == 1: d = max(d, 1 - nums[x])
    if colour[x] == 2: d = inf
  if check(1 + d):
    ok = 1 + d
    ng = inf
    while ng - ok > 1:
      m = (ok + ng) // 2
      if check(m): ok = m
      else: ng = m
    print(ok - d)
  else: print(0)
else:
  nums = [inf] * (N + 1)
  nums[1] = 1
  s = [1]
  ps = []
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
      elif colour[y] == colour[x]:
        ps.append((y, c - nums[x]))
  
  
  y, c = ps[0]
  d = 0
  if colour[y] == 1: d = c - nums[y]
  if colour[y] == 2: d = nums[y] - c

  if d % 2 or (d < 0):
    print(0)
    exit(0)
  if check(1 + d // 2): print(1)
  else: print(0)