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:
from collections import deque
n,m=map(int,input().split())
links={}
for _ in range(m):
    u,v,s=map(int,input().split())
    if u not in links:
        links[u] = [(v,s)]
    else:
        links[u].append((v,s))
    if v not in links:
        links[v]=[(u,s)]
    else:
        links[v].append((u,s))
start=1
queue=deque()
value={}
value[start]=(1,0)
queue.appendleft(start)
oppMinimum=1000000000
conflict=False #same parity on the neighbor
while queue:
    v = queue.pop()
    vx,vy=value[v]
    for (w,s) in links[v]:
        if w not in value:
            wx=s-vx
            if wx<=0:
                print(0)
                exit()
            value[w]=(wx,vy^1)
            if vy==0:
                oppMinimum=min(oppMinimum,wx)
            queue.appendleft(w)
        else:
            wx,wy=value[w]
            if vx+wx !=s:
                print(0)
                exit()
            if vy==wy:
                conflict=True
if conflict:
    print(1)
else:
    print(oppMinimum)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(100000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    g = collections.defaultdict(list)
    g2 = {}
    for _ in xrange(m):
        u, v, s = f.read_int_list()
        g[u].append((v, s))
        g[v].append((u, s))
        g2[(u,v)] = s
        g2[(v,u)] = s

    vis = [None] * (n+1)
    vis[1] = (1, 0)
    res = set()

    def dfs(v):
        for vi, si in g[v]:
            if vis[vi] is not None:
                t = tuple(sorted([v,vi]))
                res.add(t)
            else:
                vis[vi] = (vis[v][0]*-1, si-vis[v][1])
                dfs(vi)

    dfs(1)

    a = None
    for u, v in res:
        aa = vis[u][0]+vis[v][0]
        if aa == 0:
            if g2[(u,v)] != vis[u][1] + vis[v][1]: return 0
        else:
            bb = g2[(u,v)]-vis[u][1]-vis[v][1]
            a2 = bb / aa
            if aa*a2 != bb: return 0
            if a is not None and a != a2: return 0
            a = a2

    a1min = a2min = float('inf')
    a1max = a2max = -float('inf')
    for i in xrange(1,n+1):
        if vis[i][0] == 1:
            a1min = min(vis[i][1], a1min)
            a1max = max(vis[i][1], a1max)
        else:
            a2min = min(vis[i][1], a2min)
            a2max = max(vis[i][1], a2max)

    # print a1min, a1max, a2min, a2max
    if a is not None:
        return 1
    else:
        amax = a2min-1
        amin = max(1, -a1min+1)
        # print amax, amin
        if amax < amin:
            return 0
        else:
            return amax-amin+1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
# E
from collections import deque

n, m = map(int, input().split())
G = dict()
for i in range(1, n+1):
    G[i] = dict()
    
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u][v] = s
    G[v][u] = s

case = 1
done_flg = [0]*(n+1)
res_list = [0]*(n+1)
plmi_flg = [0]*(n+1)

queue = deque([1])
done_flg[1] = 1
plmi_flg[1] = 1

dif_list = []

while len(queue) > 0:
    u = queue.popleft()
    for v in G[u].keys():
        if done_flg[v] == 0:
            done_flg[v] = 1
            res_list[v] = G[u][v] - res_list[u]
            plmi_flg[v] = -plmi_flg[u]
            queue.append(v)
        elif plmi_flg[v] == -plmi_flg[u]:
            if res_list[v] != G[u][v] - res_list[u]:
                case = 9
                break
        else:
            d = G[u][v] - res_list[u] - res_list[v]
            if d % 2 == 1:
                case = 9
                break
            else:
                dif_list.append((d // 2)*plmi_flg[u])
                case = 2
            
            
# simple case
if case == 9:
    print(0)
elif case == 2:
    d = dif_list[0]
    check1 = True
    for d in dif_list:
        if d != dif_list[0]:
            check1 = False
    if check1 == False:
        print(0)
    else:
        for i in range(n+1):
            if plmi_flg[i]==1:
                res_list[i] += d
            elif plmi_flg[i]==-1:
                res_list[i] -= d
        if min(res_list[1:]) > 0:
            print(1)
        else:
            print(0)
elif case == 1:
    res_min_1 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==1])
    res_min_2 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==-1])
    r = max(0, (res_min_2 - 1) - (-res_min_1 + 1) + 1)
    print(r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(100000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    g = collections.defaultdict(list)
    g2 = {}
    for _ in xrange(m):
        u, v, s = f.read_int_list()
        g[u].append((v, s))
        g[v].append((u, s))
        g2[(u,v)] = s
        g2[(v,u)] = s

    vis = [None] * (n+1)
    vis[1] = (1, 0)
    res = set()

    def dfs(v):
        for vi, si in g[v]:
            if vis[vi] is not None:
                t = tuple(sorted([v,vi]))
                res.add(t)
            else:
                vis[vi] = (vis[v][0]*-1, si-vis[v][1])
                dfs(vi)

    dfs(1)

    a = None
    for u, v in res:
        aa = vis[u][0]+vis[v][0]
        if aa == 0:
            if g2[(u,v)] != vis[u][1] + vis[v][1]: return 0
        else:
            bb = g2[(u,v)]-vis[u][1]-vis[v][1]
            a2 = bb / aa
            if aa*a2 != bb: return 0
            if a is not None and a != aa: return 0
            a = a2

    a1min = a2min = float('inf')
    a1max = a2max = -float('inf')
    for i in xrange(1,n+1):
        if vis[i][0] == 1:
            a1min = min(vis[i][1], a1min)
            a1max = max(vis[i][1], a1max)
        else:
            a2min = min(vis[i][1], a2min)
            a2max = max(vis[i][1], a2max)

    # print a1min, a1max, a2min, a2max
    if a is not None:
        return 1
    else:
        amax = a2min-1
        amin = max(1, -a1min+1)
        # print amax, amin
        if amax < amin:
            return 0
        else:
            return amax-amin+1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
import sys


def check(k, flag=False):
    fixed = [-1] * n
    q = [(0, k, False, None)]
    while q:
        v, m, is_odd, a = q.pop()
        # print(v, m, is_odd, q, fixed)
        if fixed[v] != -1:
            p, was_odd = fixed[v]
            if is_odd == was_odd:
                if m != p:
                    return 0
                continue
            else:
                if m == p:
                    return 1
                if flag:
                    return 0
                if is_odd:
                    d = m - p
                else:
                    d = p - m
                if d < 0:
                    return 0
                if d % 2:
                    return 0
                return check(k + d // 2, True)

        fixed[v] = (m, is_odd)

        for u, s in links[v]:
            if s - m < 1:
                if not is_odd:
                    return 0
                return check(k + m - s + 1, False)
            if u == a:
                continue
            q.append((u, s - m, not is_odd, v))

    min_is_odd = float('inf')
    for m, is_odd in fixed:
        if is_odd:
            min_is_odd = min(min_is_odd, m)
    return min_is_odd


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    u, v, s = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, s))
    links[v].add((u, s))
print(check(1))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for u,v,s in a:
        e[u].append((v,s))
        e[v].append((u,s))

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[e[1][0][0]] = -1000000
    nf = set()
    q = [e[1][0][0]]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    t[0] = inf
    t2 = t[:]
    tmi = t.index(min(t))
    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[tmi] = 1
    nf = set()
    q = [tmi]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    r = inf
    if t[1:] == t2[1:]:
        return 1
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] > t2[i]:
            continue
        if r > t[i]:
            r = t[i]

    r2 = inf
    if n > 2:
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[e[1][0][0]] = -1000000
        nf = set()
        q = [e[1][0][0]]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        t[0] = inf
        t2 = t[:]
        tmi = t.index(min(t))
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[tmi] = 1
        nf = set()
        q = [tmi]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        if t[1:] == t2[1:]:
            return 1
        for i in range(1,n+1):
            if t[i] < 0:
                return 0
            if t[i] > t2[i]:
                continue
            if r2 > t[i]:
                r2 = t[i]

    return min(r,r2)



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for u,v,s in a:
        e[u].append((v,s))
        e[v].append((u,s))

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[1] = -1000000
    nf = set()
    q = [1]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    t[0] = inf
    t2 = t[:]
    tmi = t.index(min(t))
    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[tmi] = 1
    nf = set()
    q = [tmi]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    r = inf
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] > t2[i]:
            continue
        if r > t[i]:
            r = t[i]

    r2 = inf
    if n > 2:
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[e[1][0][0]] = -1000000
        nf = set()
        q = [e[1][0][0]]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        t[0] = inf
        t2 = t[:]
        tmi = t.index(min(t))
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[tmi] = 1
        nf = set()
        q = [tmi]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        for i in range(1,n+1):
            if t[i] < 0:
                return 0
            if t[i] > t2[i]:
                continue
            if r2 > t[i]:
                r2 = t[i]

    return max(min(r,r2),1)



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for u,v,s in a:
        e[u].append((v,s))
        e[v].append((u,s))

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[1] = -1000000
    nf = set()
    q = [1]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    t[0] = inf
    t2 = t[:]
    tmi = t.index(min(t))
    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[tmi] = 1
    nf = set()
    q = [tmi]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    r = inf
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] > t2[i]:
            continue
        if r > t[i]:
            r = t[i]

    r2 = inf
    if n > 2:
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[e[1][0][0]] = -1000000
        nf = set()
        q = [e[1][0][0]]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        t[0] = inf
        t2 = t[:]
        tmi = t.index(min(t))
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[tmi] = 1
        nf = set()
        q = [tmi]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        for i in range(1,n+1):
            if t[i] < 0:
                return 0
            if t[i] > t2[i]:
                continue
            if r2 > t[i]:
                r2 = t[i]

    return min(r,r2)



print(main())

Submission status: Wrong Answer

Solution code:
import sys


def check(k, flag=False):
    fixed = [-1] * n
    q = [(0, k, False)]
    while q:
        v, m, is_odd = q.pop()
        # print(v, m, is_odd, q, fixed)
        if fixed[v] != -1:
            p, was_odd = fixed[v]
            if is_odd == was_odd:
                if m != p:
                    return 0
                continue
            else:
                if m == p:
                    return 1
                if flag:
                    return 0
                if is_odd:
                    d = m - p
                else:
                    d = p - m
                if d < 0:
                    return False
                if d % 2:
                    return False
                return check(k + d // 2, True)

        fixed[v] = (m, is_odd)

        for u, s in links[v]:
            if s - m < 1:
                if not is_odd:
                    return 0
                return check(k + m - s + 1, False)

            q.append((u, s - m, not is_odd))

    min_is_odd = float('inf')
    for m, is_odd in fixed:
        if is_odd:
            min_is_odd = min(min_is_odd, m)
    return min_is_odd


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    u, v, s = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, s))
    links[v].add((u, s))
print(check(1))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for u,v,s in a:
        e[u].append((v,s))
        e[v].append((u,s))

    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[1] = -1000000
    nf = set()
    q = [1]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    t[0] = inf
    t2 = t[:]
    tmi = t.index(min(t))
    f = collections.defaultdict(bool)
    t = [None] * (n+1)
    t[tmi] = 1
    nf = set()
    q = [tmi]
    r = None
    while q:
        i = q.pop()
        for v,s in e[i]:
            if f[v]:
                continue
            if t[v] is None:
                t[v] = s - t[i]
                q.append(v)
            elif t[v] != s - t[i]:
                if v in nf:
                    return 0
                tv = (t[v] + s - t[i]) // 2
                t = [None] * (n+1)
                t[v] = tv
                nf.add(v)
                q = [v]
                break
        if nf:
            f = collections.defaultdict(bool)
        else:
            f[i] = True
    r = inf
    if t[1:] == t2[1:]:
        return 1
    for i in range(1,n+1):
        if t[i] < 0:
            return 0
        if t[i] > t2[i]:
            continue
        if r > t[i]:
            r = t[i]

    r2 = inf
    if n > 2:
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[e[1][0][0]] = -1000000
        nf = set()
        q = [e[1][0][0]]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        t[0] = inf
        t2 = t[:]
        tmi = t.index(min(t))
        f = collections.defaultdict(bool)
        t = [None] * (n+1)
        t[tmi] = 1
        nf = set()
        q = [tmi]
        while q:
            i = q.pop()
            for v,s in e[i]:
                if f[v]:
                    continue
                if t[v] is None:
                    t[v] = s - t[i]
                    q.append(v)
                elif t[v] != s - t[i]:
                    if v in nf:
                        return 0
                    tv = (t[v] + s - t[i]) // 2
                    t = [None] * (n+1)
                    t[v] = tv
                    nf.add(v)
                    q = [v]
                    break
            if nf:
                f = collections.defaultdict(bool)
            else:
                f[i] = True
        if t[1:] == t2[1:]:
            return 1
        for i in range(1,n+1):
            if t[i] < 0:
                return 0
            if t[i] > t2[i]:
                continue
            if r2 > t[i]:
                r2 = t[i]

    return min(r,r2)



print(main())