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

Solution (Python):

import sys
sys.setrecursionlimit(400000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n

check=[True]*n

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










def bfs(z):
    
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                sys.exit()
st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)
print("Yes")

Solution (Python):

import sys
sys.setrecursionlimit(100000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n

check=[True]*n

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







st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break

def bfs(z):
    
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])

st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)

for i in range(n):
    l=len(lrd[i])
    for j in range(l):
        k=lrd[i][j]
        if x[k[0]]!=x[i]+k[1]:
            print("No")
            sys.exit()
print("Yes")

Solution (Python):

from collections import deque
N, M = map(int, input().split(' '))
graph = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split(' '))
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

dsts = [float('inf') for _ in range(N)]

for n in range(N):
    if dsts[n] != float('inf'):
        continue

    buf = deque()
    buf.append(n)
    dsts[n] = 0
    while buf:
        src = buf.popleft()
        for dst, d, in graph[src]:
            next_d = dsts[src] + d

            if dsts[dst] == float('inf'):
                dsts[dst] = next_d
                buf.append(dst)

            elif dsts[dst]  != next_d:
                
                
                print("No")
                exit()

print("Yes")

Solution (Python):
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [-1]*(n+1)
        self.weight = [0]*(n+1)
    
    """ xの根を求める"""
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            y = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = y
            return y
    
    """ 木の合併 """
    def Union(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
        
        if self.rnk[rx] < self.rnk[ry]:
            self.root[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.root[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rnk[rx] == self.rnk[ry]:
                self.rnk[rx] += 1
    
    """ xとyが同じ木に所属するかの判定 """
    def IsSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ x,yのノード重みの取得 """
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
    
    """ xが属する木のサイズ(集合の個数)を取得 """
    def Size(self, x):
        return -self.root[self.Find_Root(x)]
n,m = map(int,input().split())
wuf = WeightedUnionFind(n)
flg = True
for _ in range(m):
    l,r,d = map(int,input().split())
    if not wuf.IsSameGroup(l,r):
        wuf.Union(l,r,d)
    else:
        if wuf.diff(l,r)!=d:
            flg = False
            break
print('Yes' if flg else 'No')

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(p):
    result = True
    for np, D in edge[p]:
        if pos[np] is None:
            pos[np] = pos[p] + D
            result &= dfs(np)
        else:
            if pos[p] + D != pos[np]:
                result &= False
    return result


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for q in sys.stdin.readlines():
    L, R, D = map(int, q.split())
    L -= 1; R -= 1
    edge[L].append((R, D))
    edge[R].append((L, -D))

pos = [None] * N
result = True
for i in range(N):
    if pos[i] is None:
        pos[i] = 0
        result &= dfs(i)

ans = 'Yes' if result else 'No'
print(ans)

Solution (Python):
import sys


class UnionFind():
    def __init__(self, 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


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

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

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

        if x == y:
            return

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

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

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


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

ans = 'No'
for q in sys.stdin.readlines():
    L, R, D = map(int, q.split())
    L -= 1; R -= 1

    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            break
    else:
        uf.union(L, R, D)
else:
    ans = 'Yes'

print(ans)

Solution (Python):
inf=10**10
n,m=map(int,input().split())
x=[inf]*n
con=[[] for _ in range(n)]
for i in range(m):
	l,r,d=map(int,input().split())
	con[l-1].append((r-1,d))
	con[r-1].append((l-1,-d))
from collections import deque
for i in range(n):
	if x[i]==inf:
		x[i]=0
		q=deque([i])
		while q:
			e=q.pop()
			for j,k in con[e]:
				if x[j]==inf:
					q.append(j)
					x[j]=x[e]+k
				elif x[j]!=x[e]+k:
					print("No")
					exit()
print("Yes")

Solution (Python):
inf=10**10
n,m=map(int,input().split())
x=[inf]*n
con=[[] for _ in range(n)]
for i in range(m):
	l,r,d=map(int,input().split())
	con[l-1].append((r-1,d))
	con[r-1].append((l-1,-d))
from collections import deque
for i in range(n):
	if x[i]==inf:
		x[i]=0
		q=deque([i])
		while q:
			e=q.pop()
			for j,k in con[e]:
				if x[j]==inf:
					q.append(j)
					x[j]=x[e]+k
for i in range(n):
	for j,k in con[i]:
		if x[i]+k!=x[j]:
			print("No")
			exit()
print("Yes")

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class WUnionFind:
    def __init__(self, n, sum_unity=0):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.diff_weight = [sum_unity for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return r
        
    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.diff_weight[x] = -w
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            self.diff_weight[y] = w
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1

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

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

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

n, m = na()
lrd = nan(m)
wuf = WUnionFind(n)
flag = True
for i in range(m):
    l, r, d = lrd[i]
    l -= 1
    r -= 1
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            flag = False
    else:
        wuf.unite(l, r, d)

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

def main(): 
    n,m = map(int,input().split())
    L = [[] for _ in range(n)]
    R = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        L[l].append((r,d))
        R[r].append((l,d))
    
    visited = [True] * n
    X = [0] * n

    def dfs(i):
        ans = True
        for r in L[i]:
            j, d = r
            if visited[j]:
                X[j] = X[i] + d
                visited[j] = False
                ans = (ans&dfs(j)) 
            else:
                if X[j] - X[i] != d:
                    ans = False
                    break
        for l in R[i]:
            j,d = l
            if visited[j]:
                X[j] = X[i] - d
                visited[j] = False
                ans = (ans&dfs(j))
            else:
                if X[i] - X[j] != d:
                    ans = False
                    break
        return ans
    
    ans = True
    for i in range(n):
        if visited[i]:
            visited[i] = False
            ans = (ans&dfs(i))
    
    if ans:
        print('Yes')
    else:
        print('No')        
  
if __name__=='__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
pos = [-10**10 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,-d))
stack = []
flg = 1
for i in range(1,n+1):
  if graph[i] and pos[i] == -10**10:
    stack.append(i)
    pos[i] = 0
    while stack:
      x = stack.pop()
      for y,d in graph[x]:
        if pos[y] == -10**10:
          pos[y] = pos[x]+d
          stack.append(y)
        else:
          if pos[y] != pos[x]+d:
            flg = 0
if flg:
  print("Yes")
else:
  print("No")

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""

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

data=[[] for i in range(N+1)]
for m,(l,r,d) in enumerate(LRD):
    data[l].append([r,d,m])
    data[r].append([l,-d,m])
data2=[set([m[1] for m in data[i]]) for i in range(N+1)]
Nlst=set([i for i in range(1,N)])
Mlst=set([i for i in range(M)])
visited=set()
X=[0 for i in range(N+1)]
while Mlst:
    stack=[Nlst.pop()]
    while stack:
        l=stack.pop()
        visited.add(l)
        for r,d,m in data[l]:
            if m in Mlst:
                Mlst.remove(m)
                if not r in visited:
                    visited.add(r)
                    X[r]=X[l]+d
                    stack.append(r)

                else:
                    if X[r]!=X[l]+d:
                        print("No")
                        exit()

print("Yes")

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

def dfs(v, d):
    if visited[v] and X[v] != d:
        return False
    if visited[v] and X[v] == d:
        return True
    visited[v] = True
    X[v] = d
    for u, c in E[v]:
        if not dfs(u, d + c):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    E[l].append((r, d))
    E[r].append((l, -d))
X = [None] * N
visited = [False] * N
for v in range(N):
    if not visited[v]:
        if not dfs(v, 0):
            print('No')
            exit()
print('Yes')

Solution (Python):
import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))

q=queue.Queue()
dist=[None]*N

for i in range(N):
    if dist[i]==None:
        dist[i]=0
        q.put(i)
    while not q.empty():
        From=q.get()
        for l in s[From]:
            To,w=l
            if dist[To]==None:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

Solution (Python):
import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))

q=queue.Queue()
dist=[None]*N

for i in range(N):
    if dist[i]==None:
        dist[i]=0
        q.put(i)
    while not q.empty():
        From=q.get()
        for l in s[From]:
            To,w=l
            if dist[To]==None:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
sys.setrecursionlimit(200000)
l=[None]*N
a=1
def hu(n,x):
    global a
    for i in s[n]:
        if l[i[0]]==None:
            l[i[0]]=x+i[1]
            hu(i[0],x+i[1])
        else:
            if x+i[1]!=l[i[0]]:
                a=0
for i in range(N):
    if l[i]==None:
        l[i]=0
        hu(i,0)
print("Yes" if a else "No")

Solution (Python):
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)

Solution (Python):
from collections import deque
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
llog = set()
rlog = set()
for l,r,d in zip(*[iter(L)]*3):
  dic[l].append((r,d))
  llog.add(l)
  rlog.add(r)
log = llog.difference(rlog)
q = deque(log)
dist = [-1]*(N+1)
for c in log:
  dist[c] = 0
while q:
  v = q.popleft()
  flag = False
  for u,d in dic[v]:
    if dist[u]==-1:
      dist[u] = dist[v]+d
      q.append(u)
    elif dist[u]!=dist[v]+d:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  U = llog.union(rlog)
  for c in U:
    if dist[c]==-1:
      print('No')
      break
  else:
    print('Yes')

Solution (Python):
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n)]
dist=[None]*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):
    q=deque()
    if dist[i]==None:
        dist[i]=0
        q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in G[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	L, R, D = MAP()
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))

num = [None]*N

for i in range(N):
	if num[i] != None:
		continue
	q = deque([i])
	num[i] = 0
	while q:
		n = q.popleft()
		for node, weight in graph[n]:
			if num[node] == None:
				num[node] = num[n] + weight
				q.append(node)
			else:  
				if num[node]-num[n] != weight:
					print("No")
					exit()

print("Yes")

Solution (Python):
from collections import deque

n, m = map(int, input().split())
People = {x+1:[] for x in range(10**6+1)}

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

INF = 10**10
Visited = [INF for i in range(10**6+1)]

def bfs(v):
    dq = deque()
    dq.append(v)
    Visited[v] = 0
    check = True
    while dq:
        now = dq.popleft()
        Related = People[now]
        for related in Related:
            if Visited[related[0]] == INF:
                dq.append(related[0])
                Visited[related[0]] = Visited[now] + related[1]
            elif Visited[related[0]] != Visited[now] + related[1]:
                check = False
    return check

ans = 'Yes'
for i in range(1,10**6+1):
    if Visited[i] == INF:
        if bfs(i) == False:
            ans = 'No'

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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))

visited = [False] * N
dist = [float('inf')] * N
for i in range(N):
    if not visited[i]:
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')

Solution (Python):
import sys
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append((l[i][1]-1,l[i][2]))
  connection[l[i][1]-1].append((l[i][0]-1,-l[i][2]))

distance=[-999999999999]*n
visited=[-1]*n

def bfs(v):
  distance[v]=0
  next=[v]
  next2=set()
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()

for i in range(n):
  if distance[i]==-999999999999:
    bfs(i)

for i in range(m):
  if distance[l[i][1]-1]-distance[l[i][0]-1]!=l[i][2]:
    print('No')
    sys.exit()
print('Yes')

Solution (Python):
N, M, *LRD = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for l, r, d in zip(*[iter(LRD)] * 3):
    E[l].append((r, d))
    E[r].append((l, -d))

visited = [False] * (N + 1)
D = [0] * (N + 1)
for i in range(1, N + 1):
    if visited[i]:
        continue

    S = [i]
    while S:
        v = S.pop()
        for u, d in E[v]:
            if not visited[u]:
                visited[u] = True
                D[u] = D[v] + d
                S.append(u)

            elif D[u] != D[v] + d:
                print("No")
                quit()

print("Yes")

Solution (Python):
import sys
input=sys.stdin.readline

n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,-tmp[2]])
from collections import deque
INF=10**10
dist=[INF]*n
for i in range(n):
    if dist[i]!=INF:
        continue
    dist[i]=0
    Q = deque()
    Q.append([i,0])
    while Q:
        now,cnt = Q.popleft()
        for nxt,nxt_dist in link[now]:
            if dist[nxt] == INF:
                dist[nxt] = cnt+nxt_dist
                Q.append([nxt,cnt+nxt_dist])
            elif dist[nxt] != cnt+nxt_dist:
                    print("No")
                    exit()

print("Yes")

Solution (Python):
import collections
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    flag=True
    while len(d):
        x = d.popleft()
        for i,j in vec[x]:
            if dis[i] == INF:
                dis[i]=dis[x]+j
                d.append(i)
 
            else:
                if dis[i]==dis[x]+j:
                    continue
                else:
                    print('No')
                    exit()
    return flag
 
 
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]
 
for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))
 
INF=float('inf')
dis=[INF]*n
 
for i in range(n):
    if dis[i]==INF:
        bfs(i)
print('Yes')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

INF = 10**18
N, M = map(int, input().split())
g = [[] for _ in range(N)]
lst = [INF] * N

def dfs(v):
    for n, d in g[v]:
        if lst[n] == INF:
            lst[n] = lst[v] + d
            if not dfs(n):
                return False
        else:
            if lst[n] != lst[v] + d:
                return False
    return True

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))

for i in range(N):
    if lst[i] == INF:
        lst[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')

Solution (Python):
import collections
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    flag=True
    while len(d):
        x = d.popleft()
        for i,j in vec[x]:
            if dis[i] == INF:
                dis[i]=dis[x]+j
                d.append(i)

            else:
                if dis[i]==dis[x]+j:
                    continue
                else:
                    print('No')
                    exit()
    return flag


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
dis=[INF]*n

for i in range(n):
    if dis[i]==INF:
        bfs(i)
print('Yes')

Solution (Python):
import collections
from collections import deque

def Dfs(now):
    flag = True
    d = deque()
    d.append(now)
    visited[now]=0
    while len(d):
        now = d.pop()
        for i,j in vec[now]:
            if visited[i]==INF:
                d.append(i)
                visited[i]=visited[now]+j
            else:
                if visited[i]==visited[now]+j:
                    continue
                else:
                    flag=False
                    break
    return flag


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
visited=[INF]*n

for i in range(n):
    if visited[i]==INF:
        if not Dfs(i):
            print('No')
            exit()
print('Yes')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
G = [[] for _ in range(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))
dist = [float("inf")]*n
def dfs(v):
  for nv, d in G[v]:
    if dist[nv] == float("inf"):
      dist[nv] = dist[v]+d
      if not dfs(nv):
        return False
    else:
      if dist[nv] != dist[v]+d:
        return False
  return True
for i in range(n):
  if dist[i] == float("inf"):
    dist[i] = 0
    if not dfs(i):
      print("No")
      break
else:
  print("Yes")

Solution (Python):
from collections import deque
N,M = map(int,input().split())
LRD = []
P = [float('inf') for i in range(N)]
Edges = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    Edges[R].append((L,-D))
    Edges[L].append((R,D))
for i in range(N):
    Q = deque()
    if P[i] == float('inf'):
        P[i] = 0
        Q.append(i)
    while Q:
        current_pos = Q.popleft()
        for next_pos, d in Edges[current_pos]:
            if P[next_pos] == float('inf'):
                P[next_pos] = P[current_pos] + d
                Q.append(next_pos)
            else:
                if P[next_pos] != P[current_pos] + d:
                    print('No')
                    exit()
print('Yes')

Solution (Python):
import sys
input = sys.stdin.readline


N,M=map(int,input().split())
adj=[[] for _ in range(N)]
inf = 10**9+1
x=[inf]*N

L=[0]*M
R=[0]*M
D=[0]*M
fro=[0]*N

for i in range(M):
    L[i],R[i],D[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
    adj[L[i]].append([R[i],D[i]])
    fro[R[i]]+=1
    
    
    
roots=[]
for i in range(N):
    if fro[i]==0:
        roots.append(i)

queue=[]

for root in roots:
    if x[root]==inf:
        queue.append([root,-1])
        x[root]=0
        while queue:
            node,par=queue.pop()
            num=len(adj[node])
            for i in range(num):
                to,cost=adj[node][i]
                if x[to]==inf:
                    x[to]=x[node]+cost
                    queue.append([to,node])
            
    
f=1

for i in range(M):
    d=x[R[i]]-x[L[i]]
    if d!=D[i]:
        f=0
            
    
    
            
            
            
if f==1:
    print("Yes")
else:
    print("No")

Solution (Python):

from collections import deque
n,m=map(int,input().split())
dist=[None]*n
edge=[[] for i in range(n)]

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

for i in range(n):
    q=deque()
    if dist[i]==None:
        dist[i]=0
        q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in edge[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')