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 UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################

from collections import defaultdict

N,M=map(int,input().split())
uf = UnionFind(N)
L=[0]*N
R=[0]*N
D=[0]*N
x=[-1]*N

f=1

for i in range(M):
    L[i],R[i],D[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
    uf.union(L[i],R[i])
    if x[L[i]]==-1 and x[R[i]]==-1:
        x[L[i]]=0
        x[R[i]]=D[i]
    elif x[L[i]]==-1:
        x[L[i]]=x[R[i]]-D[i]
    elif x[R[i]]==-1:
        x[R[i]]=x[L[i]]+D[i]
    else:
        if x[R[i]]-x[L[i]]!=D[i]:
            f=0
    
#範囲の判定

cnt_g=uf.group_count()
Max = defaultdict(int)
Min  = defaultdict(int)

for i in range(N):
    gi=uf.find(i)
    xx=x[i]
    Max[gi]=max(Max[gi],xx)
    Min[gi]=min(Min[gi],xx)
    
inf=10**9    

for i in range(cnt_g):
    l=Max[i]-Min[i]
    if l>inf:
        f=0
    
    
            
            
            
if f==1:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
graph = [[] * N for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    graph[L].append((R, D))
    graph[R].append((L, -D))


def dfs(node, dist):
    global visited
    global dists
    dists[node] = dist
    for next, d in graph[node]:
        if next in visited:
            if d + dist != dists[next]:
                print('No')
                sys.exit()
        else:
            visited.add(next)
            dfs(next, dist + d)


visited = set()
dists = [0] * N
for i in range(N):
    if i in visited:
        continue
    visited.add(i)
    dfs(i, 0)

print('Yes')

Submission status: Runtime Error

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

LRD = []
path = [[] for _ in range(N + 1)]
for _ in range(M):
    l, r, d = [int(_) for _ in input().split()]
    path[l].append((r, d))
    path[r].append((l, -d))
    LRD.append((l, r, d))

INF = -1e12
memo = [INF] * (N + 1)


def dfs(n):
    for ni, d in path[n]:
        if memo[ni] != INF: continue
        memo[ni] = memo[n] + d
        dfs(ni)


for i in range(1, N + 1):
    if memo[i] != INF: continue
    memo[i] = 0
    dfs(i)
for l, r, d in LRD:
    if not memo[l] + d == r:
        print('No')
        exit()
print('Yes')

Submission status: Runtime Error

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

LRD = []
path = [[] for _ in range(N + 1)]
for _ in range(M):
    l, r, d = [int(_) for _ in input().split()]
    path[l].append((r, d))
    path[r].append((l, -d))
    LRD.append((l, r, d))

memo = [None] * (N + 1)


def dfs(n):
    for ni, d in path[n]:
        if memo[ni] is not None: continue
        memo[ni] = memo[n] + d
        dfs(ni)


for i in range(N):
    if memo[i] is not None: continue
    memo[i] = 0
    dfs(i)
for l,r,d in LRD:
    if not memo[l] + d == memo[r]:

        print('No')
        exit()
print('Yes')

Submission status: Runtime Error

Solution code:
# D - People on a Line

import sys

N, M = map(int, sys.stdin.buffer.readline().split())
LRD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

LRD = [[LRD[i][0]-1, LRD[i][1]-1, LRD[i][2]] for i in range(M)]

if N == 1 or M == 0:
    print("Yes")
    exit()

neighbor = [[] for _ in range(N)]
for i in range(M):
    neighbor[LRD[i][0]].append([LRD[i][1], LRD[i][2]])
    neighbor[LRD[i][1]].append([LRD[i][0], -LRD[i][2]])

x = [None] * N

def check(i):
    if x[i] == None:
        x[i] = 0
    for next_point, dist in neighbor[i]:
        if x[next_point] == None:
            x[next_point] = x[i] + dist
            check(next_point)
        elif x[next_point] != x[i] + dist:
            print('No')
            exit()

for i in range(N):
    if x[i] == None:
        check(i)

print('Yes')

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from sys.stdin.buffer import readline

N, M = map(int, readline().split())
dic = defaultdict(list)
par = [i for i in range(N)]
rank = [0]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def unit(x, y):
  x = find(x)
  y = find(y)
  if x==y:
    return
  elif rank[x]<rank[y]:
    par[x] = y
    return
  elif rank[y]<rank[x]:
    par[y] = x
  else:
    par[y] = x
    rank[x] += 1

for i in range(M):
  l, r, d = map(int, readline().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  unit(l-1, r-1)


dist = [-1]*N
m = []
for x in range(N):
  y = find(x)
  m += [(y,0)]
  dist[y] = 0
m = set(m)
stuck = deque(m)
while stuck:
  e, a = stuck.popleft()
  flag = False
  for c in dic[e]:
    p, d = c
    x = d + dist[e]
    if dist[p]==-1:
      dist[p] = x
      stuck += [(p, x)]
    elif dist[p]!=x:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
edges = defaultdict(list)

for i in range(m):
    left, right, dist = map(int, input().split())
    edges[left-1].append((right-1, dist))
    edges[right-1].append((left-1, -dist))

seen = [None] * n
for node in range(n):
    if seen[node] is not None:
        continue

    seen[node] = 0
    todo = []
    while edges[node]:
        to, dis = edges[node].pop()
		seen[to] = dis
        todo.append([to, dis])
        
    while todo:
        new, dis = todo.pop()

        while edges[new]:
            to, n_dis = edges[new].pop()
            if seen[to] is None:
                seen[to] = dis + n_dis
            elif seen[to] != dis + n_dis:
                print('No')
                exit()
            todo.append([to, dis + n_dis])

print('Yes')

Submission status: Runtime Error

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

n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

yet = set(list(range(n)))
x_ls = [None for i in range(n)]
x_ls[0] = 0
que = deque([0])
flg = True
while len(que) > 0:
    cur = que.popleft()
    if cur in yet:
        yet.remove(cur)
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
    if len(que) == 0 and len(yet) > 0:
        que.append(list(yet)[0])
        x_ls[list(yet)[0]] = 0
        yet.pop(0)
if flg:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

yet = set(list(range(n)))
x_ls = [None for i in range(n)]
x_ls[0] = 0
que = deque([0])
flg = True
while len(que) > 0:
    cur = que.popleft()
    if cur in yet:
        yet.remove(cur)
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
    if len(que) == 0 and len(yet) > 0:
        que.append(list(yet)[0])
        x_ls[list(yet)[0]] = 0
        yet.pop(0)
if flg:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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


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

    if M == 0:
        print('Yes')
        exit()

    *LRD, = map(int, read().split())
    graph = [[] for _ in range(N + 1)]

    # 根からの距離、根は複数の可能性あり
    distance = [-1] * (N + 1)
    child = [False] * (N + 1)

    for L, R, D in zip(*[iter(LRD)] * 3):
        graph[L].append((R, D))
        child[R] = True

    for i in range(1, N + 1):
        if child[i]:
            continue

        # 以下iは根
        distance[i] = 0
        stack = [i]
        while stack:
            V = stack.pop()
            for v, d in graph[V]:
                if distance[v] == -1:
                    distance[v] = distance[V] + d
                else:
                    if distance[v] != distance[V] + d:
                        print('No')
                        exit()

                stack.append(v)

    # 例4のような循環タイプは上のfor内で処理されない
    if -1 in distance[1:]:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[]*(n+1)

	for i in li:
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import random
INF = float('inf')
N, M = map(int, input().strip().split())
LRD = [list(map(int, input().strip().split())) for _ in range(M)]

LRD.sort(key=lambda x:min(x[0], x[1]))

dic = defaultdict(lambda: INF)
for i in range(M):
	if dic[LRD[i][0]] == INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][0]] = random.randint()
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	elif dic[LRD[i][0]] == INF and dic[LRD[i][1]] != INF:
		dic[LRD[i][0]] = dic[LRD[i][1]] - LRD[i][2]
	elif dic[LRD[i][0]] != INF and dic[LRD[i][1]] == INF:
		dic[LRD[i][1]] = dic[LRD[i][0]] + LRD[i][2]
	else:
		if dic[LRD[i][0]] + LRD[i][2] == dic[LRD[i][1]]:
			continue
		else:
			print("No")
			break
else:
	print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque
INFTY = 10**10
N,M = map(int,input().split())
if N==1:
    ind = 0
else:
    G = {}
    for _ in range(M):
        L,R,D = map(int,input().split())
        if L not in G:
            G[L]=[]
        G[L].append((R,D))
        if R not in G:
            G[R] = []
        G[R].append((L,-D))
    dist = [INFTY for _ in range(N+1)]
    hist = [0 for _ in range(N+1)]
    for i in G:
        heap = deque([i])
        ind = 2
        while heap:
            cur = heap.popleft()
            if hist[cur]==0:
                dist[cur] = 0
                hist[cur]=1
                ind = 0
            elif hist[cur]==1 and ind==2:
                break
            for x in G[cur]:
                v,w = x[0],x[1]
                if hist[v]==0:
                    dist[v] = dist[cur]+w
                    heap.append(v)
                    hist[v]=1
                else:
                    if dist[v]!=dist[cur]+w:
                        ind = 1
                        break
            if ind==1:break
        if ind==1:break
if ind!=1:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import deque
INFTY = 10**10
N,M = map(int,input().split())
G = {}
for _ in range(M):
    L,R,D = map(int,input().split())
    if L not in G:
        G[L]=[]
    G[L].append((R,D))
    if R not in G:
        G[R] = []
    G[R].append((L,-D))
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
for i in G:
    heap = deque([i])
    ind = 2
    while heap:
        cur = heap.popleft()
        if hist[cur]==0:
            dist[cur] = 0
            hist[cur]=1
            ind = 0
        elif hist[cur]==1 and ind==2:
            break
        for x in G[cur]:
            v,w = x[0],x[1]
            if hist[v]==0:
                dist[v] = dist[cur]+w
                heap.append(v)
                hist[v]=1
            else:
                if dist[v]!=dist[cur]+w:
                    ind = 1
                    break
        if ind==1:break
    if ind==1:break
if ind!=1:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
INF = 10**20
N,M = map(int,input().split())
node = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int,input().split())
  node[l-1].append([r-1,d])
  node[r-1].append([l-1,-1*d])

ans = "Yes"
pos = [INF]*N
for i in range(N):
  if pos[i]==INF:
    que = [[i,0]]
    while(que):
      c,cp = que.pop()
      if pos[c]=INF:
        pos[c] = cp
        for n,d in node[c]:
          if pos[n]==INF:
            que.append([n,cp+d])
          elif pos[n] != cp+d:
            ans="No"
            break
        else:
          continue
        break
      elif pos[c] != cp:
        ans="No"
        break
    else:
      continue
    break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): yield []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(S):
        i_order = []
        temp_order = []
        level = 0
        while S:
            v1 = S.pop()
            if used[v1[0]]:
                continue
            if v1[1]<level:
                for _ in range(len(temp_order)-v1[1]):
                    x = temp_order.pop()
                    i_order.append(x)
                level = v1[1]
            level += 1
            if not used[v1[0]]:
                for v1_to in G[v1[0]]:
                    if not used[v1_to]:
                        S.append((v1_to,level))
                temp_order.append(v1[0])
                used[v1[0]] = True
        for t in reversed(temp_order):
            i_order.append(t)
        return i_order
    for i in range(N):
        if not used[i]:
            i_order = dfs([(i,0)])
            order += i_order
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = II()
L,R,D = Line(M,3)
pt = edges_to_pt(L,R,N)
label,group = scc(N,pt,pt)

x = []
used = [False]*label
for i in range(N):
    if not used[group[i]]:
        x.append(i)
        used[group[i]] = True

pt_l = [[] for _ in range(N)]
for i in range(M):
    pt_l[L[i]-1].append((R[i]-1,D[i]))
    pt_l[R[i]-1].append((L[i]-1,-D[i]))

check_visited = [False]*N
l = [None]*N 
for v in x:
    check_visited[v] = True
    l[v] = 0
    S = [v]
    while S:
        v1 = S.pop()
        for i in pt_l[v1]:
            if check_visited[i[0]] == False:
                check_visited[i[0]] = True
                l[i[0]] = l[v1] + i[1]
                S.append(i[0])
            else:
                if l[i[0]] == l[v1] + i[1]:
                    continue
                else:
                    print('No')
                    exit()

print('Yes')

Submission status: Runtime Error

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==121212:
                print(p[10])
                exit()
                
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0]) 
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==5000:
                print(p[100])
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0])
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==1000:
                print(p[100])
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0])
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==100:
                print(p[100])
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0])
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
w={}
#t={}
p,q=set(),set()
for i in range(m):
    l,r,d=[int(i) for i in input().split()]
    if l in w:
        w[l].add((r,d))
    else:
        w[l]={(r,d)}
    #t[(l,r)]=d
    p.add(l)
    q.add(r)

#print(w)
#print(t)
s=p-q
#print(s)
for i in s:
    k={j for j in w[i]}
    g=set()
    while len(k):
        x=k.pop()
        if x[0] not in w:
            g.add(x)
        else:
            for j in w[x[0]]:
                k.add((j[0],j[1]+x[1]))
    y=set()
    for j in g:
        if g[0] in y or g[0]==i:
            print("No")
            exit()
        else:
            y.add(g[0])
print("Yes")

Submission status: Runtime Error

Solution code:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n,q = m()

data = [l() for i in range(q)]

edges = [[] for i in range(n)]

for a,b,c in data:
    edges[a-1].append([b-1,c])
    edges[b-1].append([a-1,-c])

num = [0 for _ in range(n)]

Ma,mi = 0,0

vi = [False for i in range(n)]
ans = 0

for i in range(n):
    if vi[i]:
        continue
    stack = [i]
    vi[i] = True
    while stack:
        v = stack.pop()
        for e,r in edges[v]:
            if not vi[e]:
                num[e] = num[v] + d
                stack.append(e)
                vi[e] = True

for i in range(n):
    if num[i] < mi:
        mi = num[i]
    elif num[i] > Ma:
        Ma = num[i]
    for e,r in edges[i]:
        if num[i] + d != num[e]:
            ans = -1
            break
    else:
        continue
    break
else:
    print("No")
    exit()
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2000)
INF=float('inf')
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
d=[INF]*n
nbr=[[] for _ in range(n)]
used=[False]*m
for x in l:
    x[0]-=1
    x[1]-=1
#print(l)
for i in range(m):
    nbr[l[i][0]].append(i)
    nbr[l[i][1]].append(i)
#print(nbr)
def sol(i):
    if d[i]==INF:
        d[i]=0
    for x in nbr[i]:
        if used[x]:continue
        used[x]=True
        if l[x][0]==i:
            if d[l[x][1]]==INF:
                d[l[x][1]]=d[i]+l[x][2]
            elif d[l[x][1]]!=d[i]+l[x][2]:
                print('No')
                exit()
            sol(l[x][1])
        else:
            if d[l[x][0]]==INF:
                d[l[x][0]]=d[i]-l[x][2]
            elif d[l[x][0]]!=d[i]-l[x][2]:
                print('No')
                exit()
            sol(l[x][0])
for i in range(n):
    sol(i)
#print(d)
print('Yes')

Submission status: Runtime Error

Solution code:
INF=float('inf')
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
d=[INF]*n
nbr=[[] for _ in range(n)]
used=[False]*m
for x in l:
    x[0]-=1
    x[1]-=1
#print(l)
for i in range(m):
    nbr[l[i][0]].append(i)
    nbr[l[i][1]].append(i)
#print(nbr)
def sol(i):
    if d[i]==INF:
        d[i]=0
    for x in nbr[i]:
        if used[x]:continue
        used[x]=True
        if l[x][0]==i:
            if d[l[x][1]]==INF:
                d[l[x][1]]=d[i]+l[x][2]
            elif d[l[x][1]]!=d[i]+l[x][2]:
                print('No')
                exit()
            sol(l[x][1])
        else:
            if d[l[x][0]]==INF:
                d[l[x][0]]=d[i]-l[x][2]
            elif d[l[x][0]]!=d[i]-l[x][2]:
                print('No')
                exit()
            sol(l[x][0])
for i in range(n):
    sol(i)
#print(d)
print('Yes')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = IR(3)
    a -= b
    print(a % c)
    return

#B
def B():
    a, b, c, x, ans = II(), II(), II(), II(), 0
    for i in range(a + 1):
        for j in range(b + 1):
            for k in range(c + 1):
                if i * 500 + j * 100 + k * 50 == x:
                    ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(2)]
    for i in range(1, n + 1):
        dp[0][i] += dp[0][i - 1] + a[i - 1]
    a = LI()
    for i in range(1, n + 1):
        dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[i - 1]
    print(dp[1][-1])
    
    return


class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)
#D
def D():
    n, m = LI()
    u = Value_UnionFind(n)
    for _ in range(m):
        l, r, d = LI_()
        if not u.unit(l, r, d + 1):
            if u.differ(l, r) != d + 1:
                print("No")
                return
    print("Yes")


    return

#Solve
if __name__ == '__main__':
    d()