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
import sys
input = sys.stdin.readline


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_spanning_tree(graph, root):
    """与えられたグラフから全域木をつくり、二部グラフとして彩色する"""
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    """木のsからtへのパスの頂点を出力する"""
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


def judge(ans):
    """構成した解が正しいかどうか判断"""
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            return False
    return True


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    
    if not judge(ans):
        print(0)
    else:
        print(max(min_b, 0))
    
else:
    col, tree = make_spanning_tree(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
        
    if res % 2 == 1:
        print(0)
        exit()

    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [10 ** 18] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == 10 ** 18:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)

    if not judge(ans) or min(ans) <= 0:
        print(0)
    else:
        print(1)

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


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if col[a] == col[b]:
            return False
    return True

def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_spanning_tree(graph, root):
    """与えられたグラフから全域木をつくり、二部グラフとして彩色する"""
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    """木のsからtへのパスの頂点を出力する"""
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            print(0)
            exit()
    print(max(min_b, 0))
    
else:
    col, tree = make_spanning_tree(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
        
    if res % 2 == 1:
        print(0)
        exit()

    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [10 ** 18] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == 10 ** 18:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)

    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            print(0)
            exit()
    if min(ans) >= 1:
        print(1)
    else:
        print(0)

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

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x


if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    while S1[-1]==S2[-1]:
        x=S1.pop()
        S2.pop()

    

    ROOP=S1+S2[1:]+[x]
    

    score=0
    ind=0

    NOW=ROOP[-1]
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        
    

    if score%2!=0 or score<=0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[ROOP[-1]]=score//2

    Q=[ROOP[-1]]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    for i in range(1,n+1):
        if ANS[i]<=0:
            print(0)
            sys.exit()

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])


print(max(0,max(0,MIN1)+MIN0-1))

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
VUS = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]













graph = [[] for _ in range(N)]
for v, u, s in VUS:
    v -= 1
    u -= 1
    graph[v].append((u, s))
    graph[u].append((v, s))


def test():
    mi = 1
    ma = INF
    for _, w in graph[0]:
        ma = min(ma, w - 1)

    ret = 0
    for s in range(mi, ma + 1):
        ns = [None] * N
        ns[0] = s
        stack = [(0, None)]
        ok = True
        while stack:
            v, p = stack.pop()
            for u, w in graph[v]:
                if u == p:
                    continue
                if ns[u] == w - ns[v]:
                    continue
                if ns[u] is not None:
                    ok = False
                    break
                if w - ns[v] <= 0:
                    ok = False
                    break
                ns[u] = w - ns[v]
                stack.append((u, v))
        ret += ok
    print(ret)


def solve():
    odd_diffs = [None] * N
    even_diffs = [None] * N

    s = 0
    even_diffs[0] = s
    stack = [(0, s, None, True)]
    while stack:
        v, d, p, v_even = stack.pop()
        next_diffs = (odd_diffs, even_diffs)[not v_even]
        for u, w in graph[v]:
            if u == p:
                continue
            next_d = w - d
            if next_diffs[u] == next_d:
                continue
            elif next_diffs[u] is None:
                next_diffs[u] = next_d
                stack.append((u, next_d, v, not v_even))
            else:
                
                return 0

    
    ma = IINF
    mi = 1
    for v in range(N):
        
        w = INF
        for _, dw in graph[v]:
            w = min(w, dw)
        od = odd_diffs[v]
        ed = even_diffs[v]
        if od is not None and ed is not None:
            
            
            
            if (od - ed) % 2 != 0:
                return 0
            ma = min(ma, (od - ed) // 2)
            mi = max(mi, (od - ed) // 2)
        if od is not None:
            
            
            
            ma = min(ma, od - 1)
            mi = max(mi, od - w + 1)
        if ed is not None:
            
            
            
            ma = min(ma, w - ed - 1)
            mi = max(mi, -ed + 1)
    return max(0, ma - mi + 1)


ans = solve()
print(ans)

Solution (Python):
from collections import deque
import sys

n,m = map(int,input().split())

uvs = []
dic = {}

for i in range(m):

    u,v,s = map(int,input().split())
    u -= 1
    v -= 1
    uvs.append([u,v,s])

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,s])
    dic[v].append([u,s])


lis = [[0,None] for i in range(n)]

lis[0] = [0,0] 
q = deque([0])
flag = False

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        np = i[0]
        nd = i[1]

        if lis[np][1] == None:
            lis[np] = [nd-lis[now][0],lis[now][1]^1]
            q.append(np)

        elif lis[np][1] != lis[now][1]:
            if lis[np][0] != nd - lis[now][0]:
                print (0)
                sys.exit()

        else:

            new = [nd-lis[now][0],lis[now][1]^1]

            if lis[np][1] == 0:
                x = (new[0] - lis[np][0]) // 2
                flag = True
                break
            else:
                x = (lis[np][0] - new[0]) // 2
                flag = True
                break

if flag: 

    lis2 = [None] * n
    lis2[0] = x
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()
        for i in dic[now]:

            np = i[0]
            nd = i[1]

            if lis2[np] == None:
                lis2[np] = nd - lis2[now]
                q.append(np)
            elif lis2[np] != nd - lis2[now]:
                print (0)
                sys.exit()

            if min(lis2[now],lis2[np]) <= 0:
                print (0)
                sys.exit()
    
    print (1)

else: 

    m = 1
    M = float("inf")
    

    for i in range(n):

        if lis[i][1] == 0:
            m = max(m , -1 * lis[i][0] + 1)
        else:
            M = min(M , lis[i][0] - 1)

    
    print (max(0,M-m+1))

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (d-D[p]-D[np]) % 2 != 0:
                    ok = False
                    break
                if c == 1:
                    defined_n = (d-D[p]-D[np])//2
                else:
                    defined_n = (D[np]+D[p]-d)//2
                even = False
                break
            elif D[np] != d-D[p]:
                ok = False
                break
        if not ok or not even: break
    if not ok or not even: break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

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

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((v, c))
    Edge[v].append((u, c))

A = [None]*N
A[0] = (1, 0)
stack = [0]
used = set([0])
inf = 10**20
def f():
    h = None
    while stack:
        vn = stack.pop()
        a, b = A[vn]
        for vf, c in Edge[vn]:
            if vf not in used:
                A[vf] = (-a, c-b)
                stack.append(vf)
                used.add(vf)
            else:
                af, bf = A[vf]
                if a + af == 0:
                    if not b + bf == c:
                        return 0
                elif h is not None:
                    if not (a+af)*h + b + bf == c:
                        return 0
                else:
                    h2 = (c-b-bf)
                    if 1&h2:
                        return 0
                    h = h2//(a+af)
    if h is not None:
        B = [a*h + b for (a, b) in A]
        if all(b > 0 for b in B):
            return 1
        return 0
    else:
        mi = 0
        ma = inf
        for a, b in A:
            if a == 1:
                mi = max(mi, -b)
            if a == -1:
                ma = min(ma, b)
        return max(0, ma-mi-1)
print(f())

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)
            else:
                if V[sign][u] != s-val:
                    print(0)
                    exit()

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    ans = max(0, ma-mi+1)
    print(ans)

main()

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)
            else:
                if V[sign][u] != s-val:
                    print(0)
                    exit()

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    ans = max(0, ma-mi+1)

    
    
    
    
    
    
    
    
    
    
    
    
    
        
    print(ans)

main()

Solution (Python):
from collections import deque


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
others = []
UF = UnionFind(n)
for _ in range(m):
    u, v, s = map(int, input().split())
    if not UF.isSameGroup(u, v):
        adj[u].append([v, s])
        adj[v].append([u, s])
        UF.unite(u, v)
    else:
        others.append([u, v, s])

que = deque()
que.append(1)
seen = [0] * (n+1)
seen[1] = 1
val = [0] * (n+1)
plus_min = float('inf')
minus_min = float('inf')
while que:
    v = que.pop()
    for us in adj[v]:
        u, s = us
        if seen[u] == 0:
            que.append(u)
            seen[u] = -seen[v]
            val[u] = s - val[v]
            if seen[u] == -1:
                minus_min = min(minus_min, val[u])
                if minus_min <= 1:
                    print(0)
                    exit()
            else:
                plus_min = min(plus_min, val[u])

x = []
for u, v, s in others:
    if seen[u] != seen[v]:
        if val[u] + val[v] != s:
            print(0)
            exit()
    else:
        if (s - val[u] - val[v]) % 2 == 1:
            print(0)
            exit()
        x_cand = ((s - val[u] - val[v]) // 2) * seen[u]
        if x_cand <= 0:
            print(0)
            exit()
        if plus_min + x_cand <= 0 or minus_min - x_cand <= 0:
            print(0)
            exit()
        if x:
            if x_cand != x[0]:
                print(0)
                exit()
        else:
            x.append(x_cand)

if x:
    print(1)
else:
    if plus_min >= 0:
        print(max(0, minus_min - 1))
    else:
        print(max(0, minus_min - 1 - (-plus_min + 1) + 1))

Solution (Python):
N,M = map(int,input().split())
UVS = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for u,v,s in UVS:
    u-=1;v-=1
    E[u].append((v,s))
    E[v].append((u,s))

V = [None]*N
V[0] = (0,1)
q = [0]
while q:
    i = q.pop()
    d,n = V[i]
    for j,s in E[i]:
        if V[j] != None: continue
        V[j] = (1-d,s-n)
        q.append(j)

INF = 10**18
checkD = False
checkSum = []
checkMin = [INF]*2
checkMax = [-INF]*2
for i in range(N):
    for j,s in E[i]:
        if j<i: continue
        checkD = checkD or (V[i][0] == V[j][0])
        if V[i][1]+V[j][1]!=s:
            checkSum.append((V[i][0],V[j][0],s-V[i][1]-V[j][1]))
    d = V[i][0]
    checkMin[d] = min(checkMin[d],V[i][1])

if checkD:
    ansFlg = True
    cnt = set()
    for di,dj,s in checkSum:
        if di != dj:
            ansFlg = False
            break
        if di == 1: s *= -1
        cnt.add(s)
    if len(cnt)>1:
        ansFlg = False
    elif cnt:
        d = cnt.pop()
        if d%2: ansFlg = False
        d //= 2
        if min(checkMin[0]+d,checkMin[1]-d) <= 0: ansFlg = False
    ans = int(ansFlg)
else:
    ans = max(sum(checkMin)-1,0)
    if checkSum: ans = 0
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)



N,M = map(int,input().split())
UVS = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[] for _ in range(N+1)]
for u,v,s in UVS:
    graph[u].append((v,s))
    graph[v].append((u,s))

x = [None] * (N+1) 

x[1] = (0,1)
q = [1]
while q:
    v = q.pop()
    for w,s in graph[v]:
        if x[w] is not None:
            continue
        x[w] = (s-x[v][0],s-x[v][1])
        q.append(w)



INF = 10 ** 18
low, high = -INF,INF


for v in range(1,N+1):
    a,b = x[v]
    b -= a
    if b == 1:
        low = max(low, 1-a)
    else:
        high = min(high, a-1)


for u,v,s in UVS:
    a,b = x[u][0] + x[v][0], x[u][1] + x[v][1]
    b -= a
    
    if b == 0:
        if a == s:
            continue
        else:
            high = -INF
            low = INF
            break
    else:
        
        q,r = divmod(s-a,b)
        if r != 0:
            high = -INF
            low = INF
            break
        else:
            high = min(high,q)
            low = max(low,q)

answer = high - low + 1
if answer < 0:
    answer = 0
print(answer)

Solution (Python):
n, m = map(int, input().split())
u, v, s = (
    zip(*(map(int, input().split()) for _ in range(m))) if m else
    ((), (), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)




uft = UnionFindTree(n)
E = []
E_ = []
for x, y, w in zip(u, v, s):
    if uft.same(x, y):
        E_.append((x, y, w))
    if not uft.same(x, y):
        E.append((x, y, w))
        uft.union(x, y)

G = [{} for _ in range(n + 1)]
for x, y, w in E:
    G[x][y] = w
    G[y][x] = w
dp = [None for _ in range(n + 1)]
q = [1]
dp[1] = 1
W = {1}
B = set()
while q:
    x = q.pop()
    for y, w in G[x].items():
        if dp[y] is None:
            dp[y] = w - dp[x]
            if x in W:
                B.add(y)
            else:
                W.add(y)
            q.append(y)
W_min = min(dp[x] for x in W)
B_min = min(dp[x] for x in B)

d = -1
for x, y, w in E_:
    if x in W and y in W:
        D = w - dp[x] - dp[y]
        d = (
            D // 2 if D % 2 == 0 and D >= 0 and (d == -1 or D // 2 == d) else
            None
        )
    elif x in B and y in B:
        D = dp[x] + dp[y] - w
        d = (
            D // 2 if D % 2 == 0 and D >= 0 and (d == -1 or D // 2 == d) else
            None
        )
    else:
        d = (
            d if dp[x] + dp[y] == w else
            None
        )
ans = (
    0 if d is None else
    1 if 1 - W_min <= d < B_min else
    max(0, W_min + B_min - 1)
)

print(ans)

Solution (Python):
import sys
from sys import setrecursionlimit
from collections import deque
from heapq import heappop, heappush

setrecursionlimit(10**9)


def inpl(): return map(int, input().split())
INF = 2**31

N, M = inpl()
D = [[] for _ in range(N+1)]

for _ in range(M):
    u, v, s = inpl()
    D[u].append((v, s))
    D[v].append((u, s))

S = [2**31] * (N+1)
C = [-1] * (N+1)
S[1] = 0
C[1] = 0

L = [1] * (N+1)
R = [2**31] * (N+1)

Q = [1]

state = 1
while Q:
    p = Q.pop()
    for q, s in D[p]:
        if C[q] == -1:
            C[q] = int(not C[p])
            S[q] = s - S[p]
            if C[q]:
                R[q] = min(R[q], S[q] - 1)
            else:
                L[q] = max(1, -S[q] + 1)
            Q.append(q)
        elif C[q] == C[p]:
            if C[p] == 0:
                a = s - S[p]
                b = S[q]
            else:
                a = S[q]
                b = s - S[p]

            if (a-b)%2:
                state = 0
                Q = []
                break
            t = (a-b)//2
            if t == L[q] == R[q]:
                continue
            R[q] = t
            L[q] = t
            Q.append(q)


        else:
            if S[q] != s - S[p]:
                state = 0
                Q = []
                break

if state == 0:
    print(0)
elif state == 1:
    print(max(0, min(R) - max(L) + 1))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input():
    return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
cyc = [0 for _ in range(n)]
num = [10**30 for _ in range(n)]
adj = [[] for _ in range(n)]
used = [False for _ in range(m)]
for i in range(m):
    u, v, s = map(int, input().split())
    adj[u-1].append([v-1, s, i])
    adj[v-1].append([u-1, s, i])

revised_count = 0 
revised = False
novo = -1
vera = -10**30

def dfs(x):
    global revised_count, novo, vera, revised
    for v, s, e in adj[x]:
        
        if used[e]:
            
            continue
        elif num[v] > 10**20:
            cyc[v] = cyc[x]+1
            num[v] = s-num[x]
            used[e] = True
            dfs(v)
        elif num[v]+num[x] == s:
            used[e] = True
            continue
        elif (cyc[v]-cyc[x])%2 == 1:
            print(0)
            
            sys.exit()
        elif revised:
            print(0)
            
            
            sys.exit()
        elif (s-num[x]+num[v])%2 == 1:
            print(0)
            
            
            sys.exit()
        else:
            novo = v
            vera = (s-num[x]+num[v])//2
            
            revised_count += 1
            used[e] = True
    return

num[0] = 0
dfs(0)

if revised_count > 0:
    
    
    
    cyc = [0 for _ in range(n)]
    num = [10**30 for _ in range(n)]
    num[novo] = vera
    cyc[novo] = 0
    used = [False for _ in range(m)]
    revised = True
    revised_count = 0
    dfs(novo)
    for i in range(n):
        if num[i] < 0:
            print(0)
            sys.exit()
    print(1)
else:
    even = min([num[i] for i in range(n) if cyc[i]%2 == 0])
    odd = min([num[i] for i in range(n) if cyc[i]%2 == 1])
    print(max(0, even+odd-1))