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



Sample input:
3 3
1 2 3
2 3 5
1 3 4


Sample output:
1

Submission status: Wrong Answer

Solution code:
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]

    ### 閉路検出 ###
    # やるべきこと
    # DFSで閉路を見つける
    # ・奇閉路が見つかったとき
    # ⇒答えは高々一つなので探索打ち切り。
    # ⇒閉路=[a1,a2,a3,a4,a5]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5]のとき、
    # ⇒a1=((s1+s3+s5)-(s2+s4))//2 に固定される。
    # ・偶閉路が見つかったとき
    # ⇒閉路=[a1,a2,a3,a4,a5,a6]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5,s6]のとき、
    # ⇒S=s1+s3+s5-s2-s4-s6を計算する。
    # ⇒S=0ならば探索を続行する。
    # ⇒S!=0ならば0を出力して強制終了。

    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    q = [0]  # 探索用キュー
    q_dict = {0: 0}  # 頂点がqの中の何番目か
    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:
                    print("偶閉路だよ")
                    # ダメな感じの閉路なら終了、それ以外は続行
                    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)

    ### 探索終了後（奇閉路ありの場合） ###
    # ⇒先程決めた頂点からDFSをスタート。
    # ⇒矛盾が生じたら終了、生じなかったら1を出力。
    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    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)
    ### 探索終了後（奇閉路なしの場合） ###
    # ⇒どこかの頂点からDFSをスタート。
    # ⇒各頂点の取りうる値の範囲を1～10**9からスタートさせ、
    # ⇒徐々に狭めていく。
    # ⇒戻る際に過去に通った点にも随時更新をかけていく。
    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()

Submission status: Wrong Answer

Solution code:
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)
#print(colour, bipartite)
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
    for y, c in e[x]:
      ng = min(ng, c)
    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]))
  #print(ps, nums)
  
  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)

Submission status: Wrong Answer

Solution code:
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
    if min(ans) <= 0:
        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):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
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

flag = True
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]:
            flag = False

if flag:
    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
    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)

Submission status: Wrong Answer

Solution code:
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
    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)

Submission status: Wrong Answer

Solution code:
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


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
    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)

Submission status: Wrong Answer

Solution code:
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


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
    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 = [-1] * 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] == -1:
                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)