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):
from collections import defaultdict


n, m = map(int, input().split())

edges = defaultdict(list)

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

seen = [float('INF')] * n

for start in range(n):
    if seen[start] != float('INF'):
        continue

    seen[start] = 0
    todo = []
    while edges[start]:
        to, dist = edges[start].pop()
        seen[to] = dist
        todo.append([to, dist])

    while todo:
        node, dist = todo.pop()

        while edges[node]:
            to, add_dis = edges[node].pop()

            if seen[to] == float('INF') or seen[to] == dist+add_dis:
                seen[to] = dist + add_dis
                todo.append([to, dist+add_dis])

            else:
                print('No')
                exit()

print('Yes')

Solution (Python):
N, M = map(int, input().split())
LRD = [tuple(map(int, input().split())) for i in range(M)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.weight = [0]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            p = self.root(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = p
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y, w):
        w -= self.getWeight(x)
        w += self.getWeight(y)
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.weight[x] = self.weight[y]+w
            return

    def getWeight(self, x):
        x -= 1
        self.root(x)
        return(self.weight[x])


G = unionFind(N)
flag = True

for l, r, d in LRD:
    if G.same(l, r) == False:
        G.unite(l, r, d)
    else:
        if G.getWeight(l) - G.getWeight(r) == d:
            continue
        else:
            flag = False
            break

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

Solution (Python):
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    l,r,d = map(int, input().split())
    E[l-1].append((r-1, d))
    E[r-1].append((l-1, -d))

from collections import deque
human = ["0"]*N
ans = "Yes"
for i in range(N):
    if ans == "No":
        break
    if len(E[i]) == 0:
        continue
    if human[i] == "0":
        human[i] = 0
        q = deque([i])
        while q:
            temp = q.popleft()
            for e in E[temp]:
                if human[e[0]] == "0":
                    human[e[0]] = human[temp]+e[1]
                    q.append(e[0])
                elif human[e[0]] != human[temp]+e[1]:
                    ans = "No"
                    break
    else:
        for e in E[i]:
            if human[e[0]] != human[i]+e[1]:
                ans = "No"
                break

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
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')

Solution (Python):
from collections import defaultdict, deque
N, M = map(int, input().split())
used = [True]*N
dic = defaultdict(list)
for i in range(M):
  l, r, d = map(int,input().split())
  l -= 1
  r -= 1
  used[r] = False
  dic[l] += [(r,d)]

dist = [-1]*N
q = deque([])
for i in range(N):
  if used[i]:
    q += [i]
    dist[i] = 0

ans = True
while q:
  e = q.popleft()
  flag = False
  for p, d in dic[e]:
    if dist[p]==-1:
      dist[p] = d+dist[e]
      q += [p]
    elif dist[p]!=dist[e]+d:
      ans = False
      flag = True
      break
  if flag:
    break
if ans:
  if -1 not in dist:
    print('Yes')
  else:
    print('No')
else:
  print('No')

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
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 memo[l] + d != memo[r] and memo[l] - d != memo[r]:
        print('No')
        exit()
print('Yes')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

e_IN = [[] for _ in range(N+1)]
e_OUT = [[] for _ in range(N+1)]

for _ in range(M):
    l, r, d = map(int, readline().split())
    e_OUT[l].append((r, d))
    e_IN[r].append((l, d))

posx = [-1] * (N + 1)


def dfs(v):
    
    node = [v]
    posx[v] = 0
    diameter = 0
    while node:
        s = node.pop()
        ds = posx[s]
        for t, dt in e_OUT[s]:
            dist = ds + dt
            if posx[t] != -1:
                if posx[t] != dist:
                    return False
                else:
                    continue
            posx[t] = dist
            node.append(t)
            diameter = max(diameter, dist)
    if diameter <= 10 ** 9:
        return True
    else:
        return False


ans = "Yes"
for i in range(N + 1):
    if len(e_IN[i]) == 0:
        posx[i] = 0
        bl = dfs(i)
        if not bl:
            ans = "No"
            break

if - 1 in posx:
    ans = "No"

print(ans)

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

e_IN = [[] for _ in range(N+1)]
e_OUT = [[] for _ in range(N+1)]

for _ in range(M):
    l, r, d = map(int, input().split())
    e_OUT[l].append((r, d))
    e_IN[r].append((l, d))

posx = [-1] * (N + 1)


def dfs(v):
    
    node = [v]
    posx[v] = 0
    diameter = 0
    while node:
        s = node.pop()
        ds = posx[s]
        for t, dt in e_OUT[s]:
            dist = ds + dt
            if posx[t] != -1:
                if posx[t] != dist:
                    return False
                else:
                    continue
            posx[t] = dist
            node.append(t)
            diameter = max(diameter, dist)
    if diameter <= 10 ** 9:
        return True
    else:
        return False


ans = "Yes"
for i in range(N + 1):
    if len(e_IN[i]) == 0:
        posx[i] = 0
        bl = dfs(i)
        if not bl:
            ans = "No"
            break

if - 1 in posx:
    ans = "No"

print(ans)

Solution (Python):
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.weight = [0]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            p = self.root(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = p
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y, w):
        w-=self.getWeight(x)
        w+=self.getWeight(y)
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.weight[x] = self.weight[y]+w
            return
    def getWeight(self,x):
      x-=1
      self.root(x)
      return(self.weight[x])
N,M=map(int,input().split())
G=unionFind(N)
LRD=[tuple(map(int,input().split())) for i in range(M)]
for l,r,d in LRD:
  
  
  if G.same(l,r):
    if G.getWeight(r)-G.getWeight(l) == d:
      continue
    else:
      
      
      print("No")
      exit(0)
  else:
    G.unite(r,l,d)

print("Yes")

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)
def fix(x):
    q = []
    while root[x]!=x:
        q.append(x)
        x = root[x]
    rt = x
    while  len(q)>0:
        x = q.pop()
        dist[x] += dist[root[x]]
        root[x] = rt
    return rt

n,m = inm()
root = list(range(n))
dist = [0]*n
for i in range(m):
    l,r,d = inm()
    l -= 1
    r -= 1
    rtl = fix(l)
    rtr = fix(r)
    if rtl != rtr:
        
        if dist[l]+d > dist[r]:
            dist[rtr] = dist[l]+d-dist[r]
            dist[r] = dist[l]+d
            root[r] = root[rtr] = rtl
        else:
            dist[rtl] = dist[r]-dist[l]-d
            
            dist[l] = dist[r]-d
            root[l] = root[rtl] = rtr
    else:
        if dist[l]+d != dist[r]:
            print('No')
            exit()
    
    
    
print('Yes')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
data = []
inf = 10**10
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    l,r,d = map(int, input().split())
    adjacent_list[l].append([r,d])
    adjacent_list[r].append([l,-d])
finished = set()
x = [0 for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for nex, dis in adjacent_list[node]:
        if nex not in finished:
            x[nex] = x[node] + dis
            dfs(nex)
        else:
            if x[nex] != x[node] + dis:
                print("No")
                exit()
for i in range(1,n+1):
    if i not in finished:
        dfs(i)
print("Yes")

Solution (Python):


import sys
sys.setrecursionlimit(10000000)

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

Solution (Python):



class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        
        self.weight = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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

import sys
input = sys.stdin.readline  

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

for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L,R) != D:
            print("No")
            break
    else:
        uf.union(L,R,D)
else:
    print("Yes")

Solution (Python):



class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        
        self.weight = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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

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

for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L,R) != D:
            print("No")
            break
    else:
        uf.union(L,R,D)
else:
    print("Yes")

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
adjacent = [[] for _ in range(N+1)] 
for _ in range(M):
    l, r, d = lr()
    adjacent[l].append((r, d))
    adjacent[r].append((l, -d))

X = [None] * (N+1)

def check(i):
    if X[i] == None: X[i] = 0
    for target, dist in adjacent[i]:
        if X[target] == None:
            X[target] = X[i] + dist
            check(target)
        elif X[target] != X[i] + dist:
            print('No')
            exit()

for i in range(1, N+1):
    if X[i] == None:
        check(i)

print('Yes')

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
adjacent = [[] for _ in range(N+1)] 
for _ in range(M):
    l, r, d = lr()
    adjacent[l].append((r, d))
    adjacent[r].append((l, -d))

X = [None] * (N+1)
used = set()

def check(i):
    global used
    used.add(i)
    if X[i] == None: X[i] = 0
    for target, dist in adjacent[i]:
        if X[target] != None and X[target] != X[i] + dist:
            print('No')
            exit()
        if target in used:
            continue
        else:
            X[target] = X[i] + dist
            check(target)

for i in range(1, N+1):
    check(i)

print('Yes')

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

def main():
    N,M = map(int,input().split())
    dist = [[] for _ in range(N)]
    
    for i in range(M):
        l,r,d = map(int,input().split())
        dist[l-1].append((r-1,d))
        dist[r-1].append((l-1,-d))
        
    go = [None for _ in range(N)]
    for i in range(N):
        if go[i] is None:
            go[i] = 0
        q = deque([i])
        while q:
            l = q.pop()
            for r,d in dist[l]:
                if go[r] is None:
                    go[r] = go[l] + d
                    q.append(r)
                else:
                    if go[r] - go[l] != d:
                        print("No")
                        exit()
        
    print("Yes")
    
if __name__ == "__main__":
    main()

Solution (Python):
class WeightedUnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.weight = [0 for _ in range(n)]
    def find(self,x):
        root = x
        stack = [root]
        while self.parents[root] != root:
            root = self.parents[root]
            stack.append(root)
        while stack:
            s = stack.pop()
            self.weight[s] += self.weight[self.parents[s]]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y,w):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.weight[xroot] = w-self.weight[x]+self.weight[y]
        else:
            self.parents[yroot] = xroot
            self.weight[yroot] = -w+self.weight[x]-self.weight[y]
            if xrank == yrank:
                self.rank[xroot] += 1
    def diff(self,x,y):
        return self.weight[x]-self.weight[y]

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

for _ in range(M):
    l,r,d = map(int,input().split())
    if uf.find(l-1) == uf.find(r-1):
        if uf.diff(l-1,r-1) != d:
            print('No')
            break
    else:
        uf.unite(l-1,r-1,d)
else:
    print('Yes')

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

N,M = map(int,input().split())
Graph = [[] 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))

num = dict()
for i in range(N):
    if i not in num:
        num[i] = 0
        Q = deque(Graph[i])
        x = 0
        while Q:
            now,d = Q.popleft()
            if now in num:
                if num[now] != d:
                    print("No")
                    exit()
            else:
                num[now] = d
                for node,Di in Graph[now]:
                    Q.append((node,d+Di))
print("Yes")

Solution (Python):
from collections import deque
N,M = map(int,input().split())

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

num = dict()
for i in range(N):
    if i not in num:
        num[i] = 0
        Q = deque(Tree[i])
        x = 0
        while Q:
            now,d = Q.popleft()
            if now in num:
                if num[now] != d:
                    print("No")
                    exit()
            else:
                num[now] = d
                for node,Di in Tree[now]:
                    Q.append((node,d+Di))
print("Yes")

Solution (Python):
from collections import deque
N,M = map(int,input().split())

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

num = dict()
for i in range(N):
    if i not in num:
        num[i] = 0
        Q = deque(Tree[i])
        x = 0
        while Q:
            now,d = Q.popleft()
            if now in num:
                if num[now] != d:
                    print("No")
                    exit()
            else:
                num[now] = d
                for node,Di in Tree[now]:
                    Q.append((node,d+Di))
print("Yes")

Solution (Python):
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        
        self.diff_weight = [0 for i in range(n)]

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

    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 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
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.rank[x] += 1
            self.diff_weight[y] = w

n, m = map(int, input().split())
wuf = WeightedUnionFind(n)
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if wuf.find(l) == wuf.find(r):
        if wuf.diff(l, r) != d:
            print('No')
            exit()
    else:
        wuf.unite(l, r, d)
else:
    print('Yes')

Solution (Python):
N, M = map(int, input().split())
T = [[] for _ in range(N+1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    T[L].append((R, D))
    T[R].append((L, -D))
X = [None] * (N + 1)
for i in range(1, N+1):
    if X[i] is not None: continue
    X[i] = 0
    stack = [i]
    while stack:
        L = stack.pop()
        for R, D in T[L]:
            if X[R] is None:
                X[R] = X[L] + D
                stack.append(R)
            else:
                if X[R] - X[L] != D:
                    print("No")
                    exit()
print("Yes")

Solution (Python):
from collections import deque

class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

edges = [[] for _ in range(N + 1)]
tree = UnionFind(N + 1)
for _ in range(M):
    left, right, dist = map(int, input().split())
    edges[left].append((right, dist))
    edges[right].append((left, -dist))
    tree.union(left, right)

minDist = [None] * (N + 1)
for start in range(1, N + 1):
    if tree.root(start) != start:
        continue

    que = deque([(start, 0)])
    while que:
        now, dist = que.popleft()

        if minDist[now] == None:
            minDist[now] = dist
        else:
            if minDist[now] != dist:
                print('No')
                exit()
            continue

        for to, d in edges[now]:
            que.append((to, dist + d))

print('Yes')

Solution (Python):
import sys
input = sys.stdin.readline
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        
        self.weight = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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


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

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

    if uf.same(L,R):
        if uf.diff(L,R)!=D:
            print("No")
            exit()
    else:
        uf.union(L,R,-D)
        

print("Yes")

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




def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return wei[x]



def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True


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


def size(x):
    return -par[find(x)]


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




par = [-1]*n
wei = [0]*n
"""
重さが追加されるのは、yの方。
yにxの重さとwの合計が記録される。
"""
for i in range(m):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    if same(l,r):
        if d != diff(l,r):
            print("No")
            exit()
    else:
        unite(l,r,d)
print("Yes")

Solution (Python):
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            
            
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   
            self.parent[x] = y      
            return self.parent[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    
    def weighted_union(self, x, y, w):
        
        px = self.find(x)
        py = self.find(y)
        
        
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

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

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



uf = UnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    if not uf.judge(l,r):
        uf.weighted_union(l,r,d)
    else:
        if uf.weight[r]-uf.weight[l]!=d:
            print("No")
            exit()

print("Yes")

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

edge = [list(map(int,input().split())) for _ in range(M)]

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

for e in edge:
    graph[e[0]-1].append((e[1]-1,e[2]))
    graph[e[1]-1].append((e[0]-1,-e[2]))

level = [None for _ in range(N)]

inconsistent = False

for i in range(N):
    if level[i] is None:
        level[i] = 0
        stack = [i]
        while stack:
            node = stack.pop()
            for adj,cost in graph[node]:
                if level[adj] is None:
                    level[adj] = level[node] + cost
                    stack.append(adj)
                else:
                    if level[adj] != level[node] + cost:
                        inconsistent = True
                        break
    if inconsistent:
        break

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

Solution (Python):


import sys
readline = sys.stdin.readline
write = sys.stdout.write

n,m = map(int, readline().split())
*p, = range(n+1)
data = [0]*(n+1)

def root(x):
    if x == p[x]:
        return x
    r = p[x]
    p[x] = y = root(r)
    data[x] += data[r]

    return y
    
def unite(x, y, z):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        data[py] = data[x] - data[y] + z
    else:
        p[px] = py
        data[px] = data[y] - data[x] - z
    return 1


ans = []

for i in range(m):
    li,ri,di = map(int, readline().split())
    pl = root(li); pr = root(ri)
    if pl == pr:
        if data[ri] - data[li] != di:
            print("No")
            exit()
    else:
        unite(li,ri,di)

print("Yes")