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.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

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

    def union(self, x, y, 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]:
            x, y, w = y, x, -w
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weight[y] = w
        return

    def weig(self, x):
        self.find(x)
        return self.weight[x]

    def diff(self, x, y):
        return self.weigh(y) - self.weigh(x)

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
UF = WeightedUnionFind(n + 1)
for l, r, d in q:
    if UF.same(l, r):
        if d != abs(UF.diff(l, r)):
            print("No"); exit()
    else:
        UF.union(l, r, d)
print("Yes")

Submission status: Runtime Error

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

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

    def union(self, x, y, 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]:
            x, y, w = y, x, -w
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weight[y] = w
        return

    def weig(self, x):
        self.find(x)
        return self.weight[x]

    def diff(self, x, y):
        return self.weigh(y) - self.weigh(x)

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
for l, r, d in q:
    if UF.same(l, r):
        if d != abs(UF.diff(l, r)):
            print("No"); exit()
    else:
        UF.union(l, r, d)
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x,self.dist[x]
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.parents[x],self.dist[x]
    
    def union(self,x,y,d):
        rx,_=self.find(x)
        ry,_=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,*args):
        x=args[0]
        if self.parents[args[0]]<0:
            return self.dist[x],x
        else:
            self.dist[x], self.parents[x]=self.find(self.parents[x],x)
            return self.dist[args[1]]+self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x,self.parents[x])[1]
        ry=self.find(y,self.parents[x])[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        print(v.parents,v.dist)
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from heapq import heapify,heappop,heappush,heapreplace

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  n,m,*lrd=map(int,read().split())
  hp=[]
  for l,r,d in zip(*[iter(lrd)]*3):
    if l>r:
      hp.append(hp,(r,l,-d))
    else:
      hp.append(hp,(l,r,d))
  heapify(hp)
  if not hp:
    print('Yes')
    return
  while hp:
    ce=heappop(hp)
    while hp:
      ne=hp[0]
      if ce[0]==ne[0]:
        if ce[1]==ne[1]:
          if ce[2]!=ne[2]:
            print('No')
            return
          else:
            heappop(hp)
        else:
          heapreplace(hp,(ce[1],ne[1],ne[2]-ce[2]))
      else:
        break      
  print('Yes')

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from collections import deque
n , m = map(int,input().split())
z = [[] for i in range(n)]
for i in range(m):
    l , r , d = map(int,input().split())
    z[l-1].append((r-1,d))
    z[r-1].append((l-1,-d))

visit = [False for i in range(n)]
x = [-1 for i in range(n)]
for i in range(n):
    if visit[i]:
        continue
    visit[i] = True
    d = deque()
    d.append(i)
    x[i] = 0
    while d:
        now = d.popleft()
        for t , d in z[now]:
            if not visit[t]:
                visit[t] = True
                x[t] = x[now] + d
                d.append(t)
            elif visit[t]:
                if x[t] - x[now] != d:
                    print("No")
                    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
# D - People on a Line
n,m = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  e[l].append((r,d))
  e[r].append((l,-d))

INF = float('inf')
c = [INF for _ in range(n)]

def dfs(u,x):
  if c[u] == INF:
    c[u] = x
  else:
    if c[u] != x:
      print('No')
      exit()
  for v,d in e[u]:
    if c[v] != INF and c[v] == c[u]+d:
      continue
    dfs(v,c[u]+d)

for i in range(n):
  if c[i] == INF:
    dfs(i,0)
print('Yes')

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFindWeighted:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if self.parents[rx] > self.parents[ry]:
            x, y, rx, ry, w = y, x, ry, rx, -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] - w

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    N, M, *LRD = map(int, read().split())

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
root = [-10 ** 10] * N
for i in range(M):
  l, r, d = map(int, input().split())
  if (root[l] < -10 ** 9 - 1) and (root[r] < -10 ** 9 - 1):
    root[l] = 0
    root[r] = d
  elif (root[l] < -10 ** 9 - 1):
    root[l] = root[r] - d
  elif (root[r] < -10 ** 9 - 1):
    root[r] = root[l] + d
  else:
    if root[l] + d != root[r]:
      print("No")
      quit()

for i in range(N):
  if root[i] < -10 ** 9 - 1:
    root[i] = 0
    
x = min(root)
y = max(root)
if y - x > 10 ** 9:
  print("No")
  quit()
    
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pos=["-"]*N
if M==0:
  print("Yes")
  exit()
elif N==1:
  print("Yes")
  exit()
else:
  l,r,d=map(int,input().split())
pos[l-1]=0
pos[r-1]=pos[l-1]+d
for i in range(1,M):
  l,r,d=map(int,input().split())
  if pos[r-1]=="-":
    pos[r-1] = pos[l-1]+d
  elif pos[r-1]==pos[l-1]+d:
    continue
  else:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pos=["-"]*N
if M==0:
  print("Yes")
  exit()
elif n==1:
  print("Yes")
  exit()
else:
  l,r,d=map(int,input().split())
pos[l-1]=0
pos[r-1]=pos[l-1]+d
for i in range(1,M):
  l,r,d=map(int,input().split())
  if pos[r-1]=="-":
    pos[r-1] = pos[l-1]+d
  elif pos[r-1]==pos[l-1]+d:
    continue
  else:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pos=["-"]*N
if M==0:
  print("Yes")
  exit()
else:
  l,r,d=map(int,input().split())
pos[l-1]=0
pos[r-1]=pos[l-1]+d
for i in range(1,M):
  l,r,d=map(int,input().split())
  if pos[r-1]=="-":
    pos[r-1] = pos[l-1]+d
  elif pos[r-1]==pos[l-1]+d:
    continue
  else:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pos=["-"]*N
l,r,d=map(int,input().split())
pos[l-1]=0
pos[r-1]=pos[l-1]+d
for i in range(1,M):
  l,r,d=map(int,input().split())
  if pos[r-1]=="-":
    pos[r-1] = pos[l-1]+d
  elif pos[r-1]==pos[l-1]+d:
    continue
  else:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def check():
  D = defaultdict(lambda: '')
  N, M = map(int, input().split())
  if M==0:
    return 'Yes'
  for i in range(M):
    l,r,d = map(int, input().split())
    if i==0:
      D[l] = 0
    if D[r]!='' and D[l]!='' and D[r] != D[l]+d:
      return 'No'
    D[r] = D[l]+d
  if max(D.values())-min(D.values())>10**9:
    return 'No'
  return 'Yes'
print(check())

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def check():
  D = defaultdict(lambda: '')
  N, M = map(int, input().split())
  if M==0:
    return 'Yes'
  for i in range(M):
    l,r,d = map(int, input().split())
    if i==0:
      D[l] = 0
    if D[r]!='' and D[r] != D[l]+d:
      return 'No'
    D[r] = D[l]+d
  if max(D.values())-min(D.values())>10**9:
    return 'No'
  return 'Yes'
print(check())

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline

class WeightedUnionFind:
    def __init__(self, n):
        self.parents = [-1] * n
        self.rank = [0] * n
        # 根への距離を管理
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

def main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

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

check_v = [False for _ in range(n)]
check_e = [False for _ in range(n)]
max_int = 10 * 10
point = [max_int for _ in range(n)]

for v in range(n):
    Q = deque()
    Q.append(v)
    while Q:
        v = Q.popleft()
        if not check_v[v]:
            for next_v, e in graph[v]:
                if not check_e[e]:
                    if point[v] == max_int:
                        point[v] = 0
                    if point[next_v] == max_int:
                        point[next_v] = point[v] + edge[e]
                    else:
                        if point[next_v] != point[v] + edge[e]:
                            print('No')
                            exit()
                check_e[e] = True
                if not check_v[next_v]:
                    Q.append(next_v)
            check_v[v] = True
print('Yes')

Submission status: Runtime Error

Solution code:
from typing import List

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

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

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


def ok(cur: int, ds: int, dists: List[int]):
    dists[cur] = ds

    flag = True
    for nx, d in g[cur]:
        if dists[nx] >= 0:
            flag &= abs(dists[nx] - dists[cur]) == d
        elif flag:
            flag &= ok(nx, ds + d, dists)


    return flag


dists = [-1] * N
ans = True
for i in range(N):
    if ans and dists[i] < 0:
        ans &= ok(i, 0, dists)

print("Yes" if ans else "No")

Submission status: Runtime Error

Solution code:
def topo_sort(g):
    from collections import deque
    V = len(g)
    deg = [0]*V
    for src in range(V):
        for dst in g[src]:
            deg[dst] += 1
    ans = list(v for v in range(V) if deg[v]==0)
    deq = deque(ans)
    used = [0]*V

    while deq:
        v = deq.popleft()
        for t in g[v]:
            deg[t] -= 1
            if deg[t]==0:
                deq.append(t)
                ans.append(t)
    return ans

def resolve():
    N, M = list(map(int, input().split()))
    LRD = [list(map(int, input().split())) for _ in range(M)]
    adj_list = [[] for _ in range(N)]
    import numpy
    adj_matrix = numpy.full((N, N), None)
    for lrd in LRD:
        l, r, d = lrd
        adj_list[l-1].append(r-1)
        adj_matrix[l-1][r-1] = d
    
    #top_order = topological_sort(adj_list)
    top_order = topo_sort(adj_list)
    
    if len(top_order) != len(adj_list):
        print("No")
        return
    
    acc = 0
    start = top_order[0]
    now = top_order[0]
    for i in range(1, len(top_order)):
        nxt = top_order[i]
        if adj_matrix[now][nxt] is not None:
            if adj_matrix[start][nxt] is not None and acc+adj_matrix[now][nxt] != adj_matrix[start][nxt]:
                print("No")
                return
            acc += adj_matrix[now][nxt]
        now = nxt
        
    print("Yes")


if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,-c])

inf  = float("inf") 

def dfs(source):
    dist = [inf]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=inf:
                if dist[b[0]] != dist[a] +b[1]:
                    print("No")
                    exit()
            else:
                dist[b[0]] = dist[a] + b[1]
                q.append(b[0])
    return dist

dfs(min(V))

print("Yes")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
G = [[] for _ in range(n)]
INF = float("INF")
pos = [INF]*n
for _ in range(m):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    G[l].append((r,d))
    G[r].append((l,-d))

def dfs(now):
    for nxt,d in G[now]:
        if pos[nxt] == INF:
            pos[nxt] = pos[now]+d
            dfs(nxt)
        elif pos[nxt] != pos[now]+d:
            print("No")
            exit()

for i in range(n):
    if pos[i] == INF:
        pos[i] = 0
        dfs(i)
print("Yes")

Submission status: Runtime Error

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

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

L=sorted(L)
done=[float("INF")]*N
for i in range(M):
    t=L[i]
    l,r,d=t
    
    nowl=done[l]
    nowr=done[r]
    if nowl==float("INF") and nowr==float("INF"):
        done[l]=0
        done[r]=d
    elif nowl==float("INF"):
        done[l]=nowr-d
    elif nowr==float("INF"):
        done[r]=nowl+d
    else:
        if nowr-nowl!=d:
            print("No")

            exit()
ans=[]
for d in done:
    if d!=float("INF"):
        ans.append(d)
if max(ans)-min(ans)>10**9:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(s):
    global dist, visit
    q = deque()
    q.append(s)
    dist[s] = 0
    visit[s] = s
    x = 0
    y = deque()
    while q:
        p = q.popleft()
        for g in G[p]:
            if dist[g[0]] == a:
                dist[g[0]] = dist[p] + g[1] + x
                y.append(dist[g[0]])
                visit[g[0]] = s
                q.append(g[0])
            else:
                if not dist[g[0]] == dist[p] + g[1] + x:
                    if visit[g[0]] == s:
                        print("No")
                        exit()
                    else:
                        if x == 0:
                            x = dist[g[0]] - (dist[p] + g[1])
                            while y:
                                z = y.popleft()
                                dist[z] += x
                        else:
                            print("No")
                            exit()
                    

n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    l, r, d = map(int, input().split())
    G[l].append([r, d])
a = -pow(10, 9)
dist = [a] * (n + 1)
visit = [0] * (n + 1)
for i in range(1, n + 1):
    if dist[i] == a:
        bfs(i)
print("Yes")

Submission status: Runtime Error

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    if i < j:
        parent[i] += parent[j]
        parent[j] = i
    else:
        parent[j] += parent[i]
        parent[i] = j


setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
LRD = [tuple(map(int, input().split())) for _ in range(M)]
LRD.sort()

parent = [-1] * (N + 1)
for L, R, D in LRD:
    unite(parent, L, R)

d = {}
for i in range(1, N + 1):
    if parent[i] < 0:
        d[i] = 0

q = []
for L, R, D in LRD:
    if L > R:
        L, R = R, L
        D = -D
    q.append(L, R, D)

while q:
    nq = []
    for L, R, D in q:
        if L in d and R in d:
            if d[L] + D != d[R]:
                print('No')
                exit()
        elif L in d:
            d[R] = d[L] + D
        elif R in d:
            d[L] = d[R] - D
        else:
            nq.append((L, R, D))
    q = nq
print('Yes')

Submission status: Runtime Error

Solution code:
INF = 10**10

from collections import defaultdict
n,m = map(int,input().split())


visit = [False] * n
D = [INF]*n

def dfs(v, d):
  print(v,d,visit,D)
  if visit[v]:
    if D[v] != d:
      return False
    else:
      return True  
  visit[v] = True
  D[v] = d
  for nv,nd in G[v]:
    if dfs(nv, nd+D[v]):
      return False
    
  return True

ans = 'Yes'
G = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  G[l-1].append((r-1,d))
  G[r-1].append((l-1,-d))  
  
for i in range(n):
  if not visit[i] and not dfs(i,0):
    ans = 'No'
    break
  
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

from typing import List

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFindNode (object):
	__slots__ = [
		'parent_index',
		'size',
		'difference_from_parent'
	]
	
	def __init__(self, index : int, potential_identity):
		self.parent_index = index
		self.size = 1
		self.difference_from_parent = potential_identity

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			potential_abelian=IntAddition()):
		self.nodes : List[UnionFindNode] = []
		self.op = potential_abelian
		
		self.extend(num_nodes)
	
	def append(self):
		self.nodes.append(
			UnionFindNode(len(self.nodes), self.op.identity)
		)
		
	def extend(self, num_nodes):
		self.nodes.extend(
			UnionFindNode(i, self.op.identity)
			for i in range(num_nodes)
		)
	
	def root(self, index : int):
		x = self.nodes[index]
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			x.difference_from_parent = self.op.operate(
				x.difference_from_parent,
				parent.difference_from_parent
			)
			index = x.parent_index = parent.parent_index
			x = self.nodes[index]
		
		return index
	
	def difference_from_root_to(self, index : int):
		x = self.nodes[index]
		potential = x.difference_from_parent
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			potential = self.op.operate(
				potential,
				parent.difference_from_parent
			)
			index = x.parent_index
			x = self.nodes[index]
		
		return potential
		
	def size(self, index : int):
		return self.nodes[self.root(index)].size
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None) -> bool:
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.difference_from_root_to(x)
		y, py = self.root(y), self.difference_from_root_to(y)
		if x == y:
			return difference == self.op.cancel(py, px)
		
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		
		x_node = self.nodes[x]
		y_node = self.nodes[y]
		x_node.size += y_node.size
		y_node.parent_index = x
		y_node.difference_from_parent = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	valid = valid and uf.unite(L, R, D)

print('Yes' if valid else 'No')

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
if m==0:
    print("Yes")

tree = [[] for _i in range(n+1)]
for _i in range(m):
    l, r, d = map(int, input().split())
    tree[l].append([r, d])
    tree[r].append([l, -d])


from collections import deque
INF = float("inf")
visit = [INF for _i in range(n+1)]
visit[l] = 0
q = deque([l])
while q:
    p = q.popleft()
    for i, j in tree[p]:
        if i==p:
            continue
        elif visit[i] == INF:
            visit[i] = visit[p]+j
            q.append(i)
        elif visit[i] == visit[p]+j:
            continue
        else:
            print("No")
            sys.exit()
print(visit)
print("Yes")

Submission status: Runtime Error

Solution code:
visited=set()
success=1
def dfs(b,graph, node):
  global visited
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(b,graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b=[10000000000000000000]*n
  b[i]=0
  dfs(b,a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

Submission status: Runtime Error

Solution code:
visited=set()
success=1
def dfs(b,graph, node):
  global visited
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          global success
          success=0
      dfs(b,graph, graph[node-1][0][counter])
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  b=[10000000000000000000]*n
  b[i]=0
  dfs(b,a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

Submission status: Runtime Error

Solution code:
visited=set()
success=1
def dfs(graph, node):
  global b
  global visited
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          global success
          success=0
      dfs(graph, graph[node-1][0][counter])
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  b[i]=0
  dfs(a,i+1)
if success==0:
  print('No')
else:
  print('Yes')