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: Wrong Answer

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

MAX = 999999

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

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                print('No')
                exit()
    if len(next) == 0:
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                next.append(lrd[i][0])
                check = 1
        if check == 0:
            break

    temp = [] + next

print('Yes')

Submission status: Wrong Answer

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

MAX = 999999

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

a = [MAX for _ in range(n)]

a[0] = 0
temp = [0]
next = []
t = 0
s = 0
while 1:
    #print(temp)
    next = []
    #print(next)
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            #print(s, t, a)
            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                print('No')
                exit()
    if len(next) == 0:
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                next.append(lrd[i][0])
                check = 1
        if check == 0:
            print('Yes')
            exit()

    #print(next)
    temp = [] + next
    #input()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [[] for i in range(n)]
b = [[] for i in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  a[l-1].append([r-1,d])
  b[r-1].append([l-1,d])
syo = [-1] * n
from collections import deque
que = deque([])
for i in range(n):
  if b[i] == []:
    syo[i] = 0
    for j,jb in a[i]:
      syo[j] = jb
      que.append(j)
    a[i] = []
if (que == deque([]) and m != 0):
  print("No")
  exit()
while que:
  x = que.popleft()
  for i,ib in a[x]:
    if (syo[i] != syo[x]+ib and syo[i] != -1):
      print("No")
      exit()
    syo[i] = syo[x] + ib
    que.append(i)
  a[i] = []
print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

x = [None for i in range(n)]

for i in range(n):
    if x[i] == None:
        x[i] = 0
        q = deque([i])
        while len(q):
            j = q.popleft()
            for k, d in graph[j]:
                if x[k] == None:
                    q.append(k)
                    x[k] = x[j] + d
                elif x[k] != x[j] + d:
                    print("No")
                    break
else:
    print("Yes")

Submission status: Wrong Answer

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

for k in range(M):
    L, R, D = map(int, input().split())
    if P[L] == 0:
        P[L] = 1
    if P[R] == 0:
        P[R] = P[L] + D
    if P[R] - P[L] != D:
        print("No")
        exit(0)

print("Yes")

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]

for i in r:
  if z[i]==None:
    z[i]=0
  else:
    q=[i]
    while q:
      p=q.pop()
      for j,k in y[p]:
        if z[j]==None:
          q+=[j]
          z[j]=z[p]+k
        elif z[j]!=z[p]+k:
          print("No")
          exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0
  else:
    q=[i]
    while q:
      p=q.pop()
      for j,k in y[p]:
        if z[j]==None:
          q+=[j]
          z[j]=z[p]+k
        elif z[j]!=z[p]+k:
          print("No")
          exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
n,m=I()
r=range(n+1)
y=[[] for i in r]
z=[-1 for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i]+=[[j, k]]
  y[j]+=[[i,-k]]
  
for i in r:
  if z[i]<0:
    z[i],q=0,[i]
    while q:
      p=q.pop()
      for j,k in y[p]:
        if z[j]<0:
          q+=[j]
          z[j]=z[p]+k

for i in r:
  if any(z[i]+k!=z[j] for j,k in y[i]):
    print("No")
    exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
n,m=I()
r=range(n+1)
y=[[] for i in r]
z=[-1 for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i]+=[[j, k]]
  y[j]+=[[i,-k]]

for i in r:
  if z[i]<0:
    z[i]=0 
  q=[i]
  while q:
    p=q.pop()
    for j,k in y[p]:
      if z[j]<0:
        q+=[j]
        z[j]=z[p]+k
      elif z[j]!=z[p]+k:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:

N,M = [int(x) for x in input().split()]

graph = {}

for _ in range(M):
    l,r,d = [int(x) for x in input().split()]

    if l not in graph.keys():
        graph[l] = {}
        graph[l][r] = d
    else:
        if r in graph[l].keys():
            if graph[l][r] != d:
                print("No")
                exit()
        else:
            graph[l][r] = d

    for rs in graph[l]:
        if r in graph.get(rs,{}).keys():
            if (graph[rs][r]+graph[l][rs]) != graph[l][r]:
                print("No")
                exit() 

print(graph)
print("Yes")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
branch = dict()
for i in range(1,n+1):
    branch[i] = []
for i in range(m):
    l,r,d = map(int,input().split())
    branch[l].append([r,d])
    branch[r].append([l,-d])

arrival = [0 for i in range(n+1)]
arrival[0] = 1
place = [0 for i in range(n+1)]
q = [1]
check = True
p = 1
counter = 0

while counter <= n:
    if len(q) != 0:
        arrival[q[0]] = 1
        next = branch[q[0]]
        counter += 1
        for i in range(len(next)):
            if arrival[next[i][0]] == 0:
                q.append(next[i][0])
                place[next[i][0]] = place[q[0]] + next[i][1]
            else:
                if place[next[i][0]] != place[q[0]] + next[i][1]:
                    check = False
                    counter = n+1
        q.pop(0)
    else:
        while p <= n and arrival[p] == 1:
            p += 1
        if p <= n:
            q.append(p)
        else:
            counter = n+1

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

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        self.find(x)
        return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


  
N,M = map(int, input().split())
query = []
for _ in range(M):
    query.append(tuple(map(int, input().split())))
    
uf = WeightedUnionFind(N)
    
consistent = True
for l,r,d in query:
    l -= 1
    r -= 1
    if uf.isSame(l,r):
        if d != uf.diff(l,r):
            consistent = False
            break
    else:
        uf.unite(l,r,d)
        
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        if x==self.find(x):
            return 0
        else:
            self.diff_weight[x] += self.weight(self.par[x])
            return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


  
N,M = map(int, input().split())
query = []
for _ in range(M):
    query.append(tuple(map(int, input().split())))
    
uf = WeightedUnionFind(N)
    
consistent = True
for l,r,d in query:
    l -= 1
    r -= 1
    if uf.isSame(l,r):
        if d != uf.diff(l,r):
            consistent = False
            break
    else:
        uf.unite(l,r,d)
        
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        if x==self.find(x):
            return 0
        else:
            self.diff_weight[x] += self.weight(self.par[x])
            return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


  
N,M = map(int, input().split())
query = []
for _ in range(M):
    query.append(tuple(map(int, input().split())))

    
uf = WeightedUnionFind(N)
    
consistent = True
for l,r,d in query:
    l -= 1
    r -= 1
    if uf.isSame(l,r):
        if d != uf.weight(r)-uf.weight(l):
            consistent = False
            break
    else:
        uf.unite(l,r,d)
        
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

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


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

INF = float("inf")
dist = [-INF]*n

# 未探索ノードの距離を0とする
for n in range(n):
    if dist[n] != -INF:
        continue
    else:
        stack = [n]
        dist[n] = 0
        
    # stackが空になるまで探索を繰り返す
    while len(stack):
        cur = stack.pop()
        
        # ノードcurと隣り合う未探索ノードをstackに追加
        for cost, nex_node in graph[cur]:
            if dist[nex_node] != -INF:
                continue
            else:
                dist[nex_node] = dist[cur] + cost
                stack.append(nex_node)

flag = True
for i in range(n):
    if not flag:
        break
    for d,node in graph[i]:
        if dist[node]-dist[i] != d:
            print("No")
            flag = False

if flag:
    print("Yes")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l-1)
        ns.add(r-1)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    ns = {n:n for n in ns}
    while ns:
        q = [list(ns.keys())[0]]
        ns.pop(q[0])
        # print(q)
        G[q[0]] = 0
        while q:
            n = q.pop(0)
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    if r in ns:
                        ns.pop(r)
                else:
                    if G[r] != G[n] + d:
                        return 'No'
                        # pass
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    N = 100000
    M = 200000
    LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l)
        ns.add(r)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    q = [list(ns)[0]]
    G[q[0]] = 0
    while q:
        n = q.pop(0)
        for r, d in g[n]:
            if G[r] is None:
                G[r] = G[n] + d
                q.append(r)
            else:
                if G[r] != G[n] + d:
                    return 'No'
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    p = defaultdict(list)
    for l ,r, d in LRD:
        if l < r:
            p[l].append((r, d))
        else:
            p[r].append((l, -d))
    
    q = [n for n in p.keys()]
    g = {}
    while q:
        n = q.pop(0)
        if n not in p:
            continue

        x = p.pop(n)
        q = [r for r, d in x] + q
        
        if n not in g:
            g[n] = 0
        
        for r, d in x:
            pos = g[n] + d
            if r in g and g[r] != pos:
                return 'No'
            else:
                g[r] = pos
    
    return 'Yes'

def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    p = defaultdict(list)
    for l ,r, d in LRD:
        if l < r:
            p[l].append((r, d))
        else:
            p[r].append((l, -d))
    
    g = {}
    for n in p.keys():
        if n not in g:
            g[n] = 0
        
        for r, d in p[n]:
            pos = g[n] + d
            if r in g and g[r] != pos:
                return 'No'
            else:
                g[r] = pos
    
    return 'Yes'

def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L-=1
    R-=1
    if R<L:
        R,L=L,R
        D=-D
    G[L][R]=D
P=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        reached[i]=1
        while(not(q.empty())):
            p=q.get()
            for r in G[p]:
                q.put(r)
                if reached[r]==0:
                    P[r]=P[p]+G[p][r]
                else:
                    if P[r]!=P[p]+G[p][r]:
                        print("No")
                        exit()
                reached[r]=1
print("Yes")

Submission status: Wrong Answer

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L-=1
    R-=1
    if R<L:
        R,L=L,R
        D=-D
    G[L][R]=D
P=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        while(not(q.empty())):
            p=q.get()
            for r in G[p]:
                q.put(r)
                if reached[r]==0:
                    P[r]=P[p]+G[p][r]
                else:
                    if P[r]!=P[p]+G[p][r]:
                        print("No")
                        exit()
                reached[r]=1
print("Yes")

Submission status: Wrong Answer

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L-=1
    R-=1
    if R<L:
        R,L=L,R
        D=-D
    G[L][R]=D
P=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        while(not(q.empty())):
            p=q.get()
            for r in G[p]:
                q.put(r)
                if reached[r]==0:
                    P[r]=P[p]+G[p][r]
                    reached[r]=1
                else:
                    if P[r]!=P[p]+G[p][r]:
                        print("No")
                        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L-=1
    R-=1
    G[L][R]=D
P=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        while(not(q.empty())):
            p=q.get()
            for r in G[p]:
                q.put(r)
                if reached[r]==0:
                    P[r]=P[p]+G[p][r]
                    reached[r]=1
                else:
                    if P[r]!=P[p]+G[p][r]:
                        print("No")
                        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    L = [0 for _ in range(M)]
    R = [0 for _ in range(M)]
    D = [0 for _ in range(M)]
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] = L[i] - 1
        R[i] = R[i] - 1

    x = [0 for _ in range(N)]
    flag = [0 for _ in range(N)]
    for i in range(M):
        if flag[L[i]]==flag[R[i]]==0:
            x[L[i]] = 0
            x[R[i]] = x[L[i]] + D[i]
            flag[L[i]] = 1
            flag[R[i]] = 1
        elif flag[L[i]]==flag[R[i]]==1:
            if x[R[i]]-x[L[i]] != D[i]:
                return "No"
        else:
            if flag[L[i]]==1:
                x[R[i]] = x[L[i]] + D[i]
                flag[R[i]] = 1
            else:
                x[L[i]] = x[R[i]] - D[i]
                flag[L[i]] = 1
    return "Yes"

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    lpd, rpd = Distance[l][1], Distance[r][1]

    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d + lpd
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d - rpd
    else:
        if rpd - lpd != d:
            print("No")
            exit()

print("Yes")

Submission status: Wrong Answer

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

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    lpd, rpd = Distance[l][1], Distance[r][1]

    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d + lpd
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d - rpd
    else:
        if rpd - lpd != d:
            print("No")
            exit()
    print(Group, Distance)
print("Yes")

Submission status: Wrong Answer

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

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d
    else:
        if not Distance[r][1] - Distance[l][1] == d:
            print("No")
            exit()

print("Yes")

Submission status: Wrong Answer

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

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d
    else:
        if not Distance[r][1] - Distance[l][1] == d:
            exit()

print("Yes")

Submission status: Wrong Answer

Solution code:

N, M = map(int, input().split())
Info = [list(map(int, input().split())) for i in range(M)]

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    print(info, lp, rp)
    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d
    else:
        if not Distance[r][1] - Distance[l][1] == d:
            print("No")
            exit()

print("Yes")