Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Runtime Error

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.par_weight[x] += self.par_weight[self.parents[x]]
            self.parents[x] = root
            return self.parents[x]

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [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])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def GetWeight(self, x):
      self.Find_Root(self, x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return abs(self.GetWeight(y)- self.GetWeight(xs))
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True

  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.isSameGroup(l, r):
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
from timeout_decorator import timeout, TimeoutError



@timeout(1.8)
def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    dist_ind = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d
        dist_ind[(l, r)] = i
        dist_ind[(r, l)] = i

    position = ['x' for i in range(num + 1)]
    dist_visit = [0 for i in range(hint_num)]
    check_point = [0 for i in range(num + 1)]

    flg = 1
    for i in range(hint_num):
        if dist_visit[i]:
            continue
        # dist_visit[i] = 1

        l, r, d = data[i]
        now_set = set()
        next_set = set()
        now_set.add(l)
        now_set.add(r)

        while len(now_set) > 0:
            for now_ele in now_set:
                if position[now_ele] == 'x':
                    position[now_ele] = 0

                for next_ele in graph_data[now_ele]:
                    if check_point[next_ele]:
                        continue
                    length = dist_data[(now_ele, next_ele)]
                    len_ind = dist_ind[(now_ele, next_ele)]
                    if dist_visit[len_ind]:
                        continue
                    dist_visit[len_ind] = 1
                    if position[next_ele] == 'x':
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
                check_point[now_ele] = 1
            now_set = next_set
            next_set = set()

    # print(position)

    max_data = -10 ** 10
    min_data = 10 ** 10
    for i in range(1, num + 1):
        if position[i] == 'x':
            continue
        max_data = max(max_data, position[i])
        min_data = min(min_data, position[i])

    if max_data - min_data > 10 ** 9:
        flg = 0

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    try:
        main()
    except:
        print('No')

Submission status: Runtime Error

Solution code:
# 参考: https://qiita.com/y-tsutsu/items/aa7e8e809d6ac167d6a1

from heapq import heappush, heappop


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

# 多次元配列
# dp = [[0] * 3 for _ in range(5)


class Edge:
    def __init__(self, to: int, cost: int):
        self._to = to
        self._cost = cost

    @property
    def to(self):
        return self._to

    @property
    def cost(self):
        return self._cost


class Edges(list):
    def __init__(self):
        list.__init__(self)


INF = 1 << 28
MOD = int(1e9) + 7


def dijkstra(graph, s: int):
    n = len(graph)
    dist = [INF for _ in range(n)]
    cnts = [0 for _ in range(n)]

    pq = []
    heappush(pq, (0, s))
    dist[s] = 0
    cnts[s] = 1

    while pq:
        (cost, cur) = heappop(pq)

        if dist[cur] != cost:
            continue

        for next in graph[cur]:
            if dist[next.to] > cost + next.cost:
                heappush(pq, (cost + next.cost, next.to))
                dist[next.to] = cost + next.cost
                cnts[next.to] = cnts[cur]
            elif dist[next.to] == cost + next.cost:
                cnts[next.to] = (cnts[next.to] + cnts[cur]) % MOD

    return dist, cnts


# 入力を受け取る
n, m = map(int, input().split())

s, t = map(lambda i: int(i) - 1, input().split())

g = [Edges() for _ in range(n)]

for _ in range(m):
    u, v, d = map(int, input().split())
    g[u - 1].append(Edge(v - 1, d))
    g[v - 1].append(Edge(u - 1, d))

dst1, cnt1 = dijkstra(g, s)
dst2, cnt2 = dijkstra(g, t)

ret = cnt1[t] * cnt1[t] % MOD

for i in range(n):
    if 2 * dst1[i] == dst1[t]:
        sub = cnt1[i] * cnt1[i] % MOD
        sub = sub * cnt2[i] % MOD * cnt2[i] % MOD
        ret = (ret + MOD - sub) % MOD

sum_sub = 0
for u in range(n):
    for e in g[u]:
        v, d = e.to, e.cost
        if 2 * dst1[u] < dst1[t] < 2 * dst1[v] and dst1[u] + d == dst1[v] and dst2[v] + d == dst2[u]:
            sub = cnt1[u] * cnt1[u] % MOD
            sub = sub * cnt2[v] % MOD * cnt2[v] % MOD
            sum_sub = (sum_sub + sub) % MOD

ret = (ret + MOD - sum_sub) % MOD
print(ret)

Submission status: Runtime Error

Solution code:
# 参考: https://qiita.com/y-tsutsu/items/aa7e8e809d6ac167d6a1

from typing import List, Tuple
from heapq import heappush, heappop


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

# 多次元配列
# dp = [[0] * 3 for _ in range(5)


class Edge:
    def __init__(self, to: int, cost: int):
        self._to = to
        self._cost = cost

    @property
    def to(self):
        return self._to

    @property
    def cost(self):
        return self._cost


class Edges(list):
    def __init__(self):
        list.__init__(self)


INF = 1 << 28
MOD = int(1e9) + 7


def dijkstra(graph: List[Edges], s: int) -> Tuple[List[int], List[int]]:
    n = len(graph)
    dist = [INF for _ in range(n)]
    cnts = [0 for _ in range(n)]

    pq: List[Tuple[int, int]] = []
    heappush(pq, (0, s))
    dist[s] = 0
    cnts[s] = 1

    while pq:
        (cost, cur) = heappop(pq)

        if dist[cur] != cost:
            continue

        for next in graph[cur]:
            if dist[next.to] > cost + next.cost:
                heappush(pq, (cost + next.cost, next.to))
                dist[next.to] = cost + next.cost
                cnts[next.to] = cnts[cur]
            elif dist[next.to] == cost + next.cost:
                cnts[next.to] = (cnts[next.to] + cnts[cur]) % MOD

    return dist, cnts


# 入力を受け取る
n, m = map(int, input().split())

s, t = map(lambda i: int(i) - 1, input().split())

g = [Edges() for _ in range(n)]

for _ in range(m):
    u, v, d = map(int, input().split())
    g[u - 1].append(Edge(v - 1, d))
    g[v - 1].append(Edge(u - 1, d))

dst1, cnt1 = dijkstra(g, s)
dst2, cnt2 = dijkstra(g, t)

ret = cnt1[t] * cnt1[t] % MOD

for i in range(n):
    if 2 * dst1[i] == dst1[t]:
        sub = cnt1[i] * cnt1[i] % MOD
        sub = sub * cnt2[i] % MOD * cnt2[i] % MOD
        ret = (ret + MOD - sub) % MOD

sum_sub = 0
for u in range(n):
    for e in g[u]:
        v, d = e.to, e.cost
        if 2 * dst1[u] < dst1[t] < 2 * dst1[v] and dst1[u] + d == dst1[v] and dst2[v] + d == dst2[u]:
            sub = cnt1[u] * cnt1[u] % MOD
            sub = sub * cnt2[v] % MOD * cnt2[v] % MOD
            sum_sub = (sum_sub + sub) % MOD

ret = (ret + MOD - sum_sub) % MOD
print(ret)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = [[] for i in range(N+1)]

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in L[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d :
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

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

P=[i for i in range(N+1)]
r=[0 for i in range(N+1)]

def find(a):
    if a==P[a]:
        pass
    else:
        return find(P[a])
        
def union(a,b,c):
    P[b]=a
    r[b]=c
    
def find2(a,b):
    if a==P[a]:
        return b+r[a]
    else:
        return find2(P[a],b+r[a])
L=[]
for i in range(M):
    a,b,c=map(int,input().split())
    union(a,b,c)
    L.append([a,b,c])
    
for i in range(1,N+1):
    r[i]=find2(i,0)
    
#print(r)
#print(P)

for i in L:
    if r[i[0]]!=r[i[1]]-i[2]:
        print(i)
        print("No")
        exit()
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
Adj_list = [[] for _ in range(N) ]

for i in range(M):
    a, b, c = map(int, input().split())
    Adj_list[a-1].add((b-1, c))
    Adj_list[b-1].add((a-1, -c))
visited =[None]*(N)
ok = True
stack = []
for x in range(N):
   if visited[x] is not None:continue
   visited[x] = 0
   stack = [x]
   while stack:
       v = stack.pop()
       for to,d in Adj_list[v]:
           if visited[to] is None:
               visited[to] = G[v] + d
               stack.append(to)
           else:
               if G[to] != G[v]+d:
                   ok = False
                   break
   if ok == False:
        break
print("Yes" if ok else "No")

Submission status: Runtime Error

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = float("inf")


N,M = map(int,input().split())
Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    Adj_list[a-1].add((b-1, c))
    Adj_list[b-1].add((a-1, -c))
visited =[None]*(N)
ok = True
stack = []
for x in range(N):
   if visited[x] is not None:continue
   visited[x] = 0
   stack = [x]
   while stack:
       v = stack.pop()
       for to,d in Adj_list[v]:
           if visited[to] is None:
               visited[to] = G[v] + d
               stack.append(to)
           else:
               if G[to] != G[v]+d:
                   ok = False
                   break
   if ok == False:
        break
print("Yes" if ok else "No")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    Adj_list[a-1].add((b-1, c))
    Adj_list[b-1].add((a-1, -c))
visited =[None]*(N)
ok = True
stack = []
for x in range(N):
   if visited[x] is not None:continue
   visited[x] = 0
   stack = [x]
   while stack:
       v = stack.pop()
       for to,d in Adj_list[v]:
           if visited[to] is None:
               visited[to] = G[v] + d
               stack.append(to)
           else:
               if G[to] != G[v]+d:
                   ok = False
                   break
   if ok == False:
        break
print("Yes" if ok else "No")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
LRD = list(list(map(int,input().split())) for i in range(M))
#print(LRD)
d = {LRD[0][0]:0}

for i in range(M):
    if (LRD[i][0] in d) and (LRD[i][1] not in d):
          d[LRD[i][1]] = d[LRD[i][0]]+LRD[i][2]
    elif (LRD[i][0] in d) and (LRD[i][1] in d):
        if d[LRD[i][1]] != d[LRD[i][0]]+LRD[i][2]:
            print("No")
            exit()
    elif (LRD[i][0] not in d) and (LRD[i][1] in d):
        d[LRD[i][0]] = d[LRD[i][1]] - LRD[i][2]
    else:
        d[LRD[i][0]] = 0
        d[LRD[i][1]] = d[LRD[i][0]] + LRD[i][2]

print("Yes")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int, input().split())
input = sys.stdin.readline()
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [-1] * (N+1)
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

def root(x):
    if data[x] == x:
        return x
    else:
        r = root(x)
        diff_weight[x] += diff_weight[ data[x] ]
        data[x] = r
        return r

def weight(x):
    _ = root(x)
    return diff_weight[x]


def diff(x,y):
    return weight(y) - weight(x)

def merge(x,y,w):
    w  += weight(x); w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y: return False
    if rank[x] < rank[y]: x,y = y,x; w = -w
    if rank[x] == rank[y]: rank[x] += 1
    data[y] = x
    diff_weight[y] = w
    return True

def issame(x,y):
    return root(x) == root(y)

for i in range(M):
    L,R,D = LRD[i]
    if not issame(L,R):
        merge(L,R,D)
    else:
        if weight(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

lrds = [tuple(map(int, input().split())) for _ in range(m)]

xs = [None for _ in range(n)]

ps = [[] for _ in range(n)]

for lrd in lrds:
    l, r, d = lrd
    ps[l-1].append((r-1, d))
    ps[r-1].append((l-1, -d))

not_decided = set(range(n))

def f(t):
    for p in ps[t]:
        another, relative_position = p
        if another in not_decided:
            xs[another] = xs[t] + relative_position
            not_decided.remove(another)
            f(another)
        else:
            if xs[another] != xs[t] + relative_position:
                return False
    return True

def solve():
    while len(not_decided) != 0:
        t = not_decided.pop()
        xs[t] = 0

        if not f(t):
            return False
    return True

if solve():
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

lrds = [tuple(map(int, input().split())) for _ in range(m)]

xs = [None for _ in range(n)]

ps = [[] for _ in range(n)]

for lrd in lrds:
    l, r, d = lrd
    ps[l-1].append((l-1, r-1, d))
    ps[r-1].append((l-1, r-1, d))

not_decided = set(range(n))

def f(t):
    for lrd in ps[t]:
        l, r, d = lrd
        if l == t:
            another = r
            position = d
        else:
            another = l
            position = -d
        if xs[another] is None:
            xs[another] = xs[t] + position
            not_decided.remove(another)
            f(another)
        else:
            if xs[another] != xs[t] + position:
                return False
    return True

def solve():
    while len(not_decided) != 0:
        t = not_decided.pop()
        xs[t] = 0

        if not f(t):
            return False
    return True

if solve():
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
Inf = 10000000000
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))
 
Node = [Inf for i in range(N)]
Possible = True
for i in range(N):
    if not Possible:
        break
    elif Node[i] == Inf:
        Node[i] = 0
        Q = [i]
        while Q:
            now = deque.popleft(Q)
            for e in Edge[now]:
                if Node[e[0]] == Inf:
                    Node[e[0]] = Node[now] + e[1]
                    Q.append(e[0])
                elif Node[now] + e[1] != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    
ans = 'Yes'
N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if not X.union(l-1, r-1, d):
        ans = 'No'

print(ans)

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    

N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if not X.union(l-1, r-1, d):
        ans = 'No'
else:
    ans = 'Yes'
print(ans)

Submission status: Runtime Error

Solution code:
setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

'''
for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
'''
print("Yes")

Submission status: Runtime Error

Solution code:
setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)


for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()

print("Yes")

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

  '''
for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
            '''
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (i,i)
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (i,i)
    visited[i] = True
    (n,m) = ( - inf, inf)
    for j,d in edges[i]:
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

for i in range(N):
    # 連結成分のminとmax
    (n,m) = walk(i)
    if m -n > 10 ** 9:
        print("No")
        exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M = list(map(int,input().split()))

edges = defaultdict(dict)

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[ L - 1][R -1] = D
    edges[R - 1][L - 1] = -D


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (i,i)
    visited[i] = True
    (n,m) = ( inf, -inf)
    for j,d in edges[i].items():
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

for i in range(N):
    # 連結成分のminとmax
    (n,m) = walk(i)
    if m -n > 10 ** 9:
        print("No")
        exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
Graph=[[] for i in range(N)]
for i in range(M):
  L,R,D=map(int,input().split())
  Graph[L-1].append(R-1,D)
  Graph[R-1].append(L-1,-D)
visit=[False]*N
dist=[0]*N

for i in range(N):
  if not visit[i]:
    visit[i]=True
    A=deque()
    A.append(i)
    while A:
      x=A.pop()
      for y,d in Graph[x]:
        if visit[y] and dist[y]!=d+dist[x]
        	print('No')
          	exit()
        elif not visit[y]:
          visit[y]=True
          A.append(y)
          dist[y]=d+dist[x]
print('Yes')

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x):	#xの根を返す
	global table
	global diff_weight
	
	if table[x] == x:
		return x
	else:
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x) 
	x = find(x)	
	y = find(y)
	
	if x == y:
		return
	
	if rank[x] < rank[y]:
		x,y = y,x
		w = -w
	
	table[y] = x
	diff_weight[y] = w
	
	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]
		
def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))

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

table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(M):
	a,b,D = (map(int,input().split()))
	a -= 1
	b -= 1
	if check(a,b):
		if diff(a,b) != D:
			print ('table',table)
			print ('weight',diff_weight)
			print('No')
			sys.exit()
	else:
		union(a,b,D)
	print ('table',table)
	print ('weight',diff_weight)
	
	
print ('Yes')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

class Impossible(ValueError):
    pass

def main():
    n, m = map(int, input().split())
    lrds = []
    for i in range(m):
        l, r, d = map(int, input().split())
        lrds.append((l - 1, r - 1, d))

    adj = [[] for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        l, r, d = lrds[i]
        union(parents, l, r)
        adj[l].append((r, d))
        adj[r].append((l, -d))

    ds = set()
    for i in range(n):
        ds.add(find(parents, i))

    pos = [None for i in range(n)]
    try:
        for i in ds:
            pos[i] = 0
            dfs(adj, pos, i)
        print("Yes")
    except Impossible:
        print("No")

def dfs(adj, pos, x):
    for y, d in adj[x]:
        if pos[y] is None:
            pos[y] = pos[x] + d
            dfs(adj, pos, y)
        elif pos[y] != pos[x] + d:
            raise Impossible

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

def union(p, x, y):
    p[find(p, y)] = find(p, x)


main()