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):
class DSUWeighted():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n
        self.wt = [0] * n

    def leader(self, a):
        
        x = a
        order = [x]
        while self.par_size[x] >= 0:
            x = self.par_size[x]
            order.append(x)
        for s in order[:-1][::-1]:
            self.wt[s] += self.wt[self.par_size[s]]
            self.par_size[s] = x
        return x

    def same(self, a, b):
        
        
        return self.leader(a) == self.leader(b)

    def merge(self, a, b, w):
        
        
        x = self.leader(a)
        y = self.leader(b)
        w += self.wt[a] - self.wt[b]
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w = -w
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

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

import sys
input = sys.stdin.buffer.readline

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

uf = DSUWeighted(N)

for _ in range(M):
    l, r, d = map(int, input().split())
    if uf.same(l - 1, r - 1):
        if uf.diff(l - 1, r - 1) != d:
            print('No')
            break
    else:
        uf.merge(l - 1, r - 1, 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 is_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())

wuf = WeightedUnionFind(N+1)

ans = 'Yes'
for i in range(M):
    L, R, D = map(int, input().split())

    if wuf.is_same(L, R):
        if wuf.diff(L, R) != D:
            ans = 'No'
            break
    else:
        wuf.union(L, R, D)

print(ans)

Solution (Python):
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0] * n


def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x, y, z):
    s, ws = find(x)
    t, wt = find(y)
    
    if s == t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        if ws < z + wt:
            par[s] = t
            diff[s] = z + wt - ws
        else:
            par[t] = s
            diff[t] = ws - z - wt


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

print('Yes')

Solution (Python):



import sys
sys.setrecursionlimit(10001000)

class UnionFindWeighted:
    def __init__(self, n):                      
        self.n = n                              
        self.parents = [i for i in range(n)]    
        self.ranks = [0] * n                    
        self.sizes = [1] * n                    
        self.weights = [0] * n                  

    def find(self, x):          
        if self.parents[x] == x:
            return x
        else:
            p = self.find(self.parents[x])
            self.weights[x] += self.weights[self.parents[x]]
            self.parents[x] = p
            return p

    def unite(self, x, y, w):          
        
        rx = self.find(x)
        ry = self.find(y)
        wx = self.weight(x)
        wy = self.weight(y)
        if rx == ry: return
        if self.ranks[rx] > self.ranks[ry]:
            rx , ry = ry, rx    
            wx , wy = wy, wx
            w *= -1
            print("a")
        self.parents[rx] = ry
        self.sizes[ry] += self.sizes[rx]
        self.weights[rx] = wy - wx - w
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[rx] += 1

    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 size(self, x):          
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            
        return {i for i, x in enumerate(self.parents) if i == x}

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

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

    def weight(self, x):       
        _ = self.find(x)
        return self.weights[x]

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

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



n, m = map(int, input().split())
uf = UnionFindWeighted(n)
for _ in range(m):
    a, b, w = map(int,input().split())
    a -= 1
    b -= 1
    if uf.same(a, b):
        if uf.diff(a, b)!=w:
            print('No')
            exit()
    else:
        uf.unite(a, b, w)
print('Yes')

Solution (Python):
class WeighttedUnionFind:
	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())
wuf = WeighttedUnionFind(N)

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

	if not wuf.same(l, r):
		wuf.union(l, r, d)

	else:
		if wuf.diff(l, r) !=d:
			print("No")
			exit()
print("Yes")

Solution (Python):
class WeightedUnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
        self.diff_weight = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        r = self.find(self.parent[x])
        self.diff_weight[x] += self.diff_weight[self.parent[x]]
        self.parent[x] = r
        return r
    
    def unite(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.diff_weight[y] = w

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

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

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

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.same(l,r) and uf.diff(l,r) != d:
        print("No")
        exit()
    uf.unite(l,r,d)
print("Yes")

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


class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [[] for _ in range(self.n)]
        self.dist = [None] * self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))

    def bfs(self, start, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.dist = [None] * self.n
        p, t, dist = start, time, 0
        self.dist[p] = 0
        next_set = deque([(p, t, dist)])

        while next_set:
            p, t, dist = next_set.popleft()
            for edge in self.edges[p]:
                q, cost = edge.to, edge.cost
                if self.dist[q] is not None:
                    if self.dist[q] != dist + cost:
                        print("No")
                        exit()
                    continue
                self.dist[q] = dist + cost
                next_set.append((q, t + 1, dist + cost))
        return True



N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)
    graph.add_edge(y, x, -cost)
for i in range(1,N+1):
    if graph.dist[i-1] is None:
        graph.bfs(i, goal=-1, time=0, save=True)
print("Yes")

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

def f(hito, zahyo):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1])
    else:
      if x[tsugi[0]]!=zahyo+tsugi[1]:
        print('No')
        exit()

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
  l, r, d=map(int, input().split())
  links[l].append([r, d])
  links[r].append([l, -d])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None:
    f(i, 0)
    
print('Yes')

Solution (Python):
def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        p = find(par[x])
        diff_w[x] += diff_w[par[x]]
        par[x] = p
        return p


def weight(x):
    '''
    xの根からの距離を求める
    '''
    find(x)
    return diff_w[x]


def union(x, y, w):
    '''
    w[y] = w[x] + w となるようにxとyの属する集合を併合する
    '''
    w += weight(x) - weight(y)
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x
        w = -w
    par[x] += par[y]
    par[y] = x
    diff_w[y] = w
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


def size(x):
    '''
    xが属する集合の個数を求める
    '''
    return -par[find(x)]


def diff(x, y):
    '''
    xとyが同じ集合に属するときの w[y] - w[x] を求める
    '''
    return weight(y) - weight(x)


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

par = [-1] * n
diff_w = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())

    if same(l-1, r-1):
        if diff(l-1, r-1) != d:
            print('No')
            exit()
    else:
        union(l-1, r-1, d)

print('Yes')

Solution (Python):
def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        p = find(par[x])
        diff_w[x] += diff_w[par[x]]
        par[x] = p
        return p


def weight(x):
    '''
    xの根からの距離を求める
    '''
    find(x)
    return diff_w[x]


def union(x, y, w):
    '''
    w[y] = w[x] + w となるようにxとyの属する集合を併合する
    '''
    w += diff_w[x] - diff_w[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x
        w = -w
    par[x] += par[y]
    par[y] = x
    diff_w[y] = w
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


def size(x):
    '''
    xが属する集合の個数を求める
    '''
    return -par[find(x)]


def diff(x, y):
    '''
    xとyが同じ集合に属するときの w[y] - w[x] を求める
    '''
    return weight(y) - weight(x)


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

par = [-1] * n
diff_w = [0] * n

for _ in range(m):
    l, r, d = map(int, input().split())

    if same(l-1, r-1):
        if diff(l-1, r-1) != d:
            print('No')
            exit()
    else:
        union(l-1, r-1, d)

print('Yes')

Solution (Python):
def find(x, U, r, w): 
  if x == U[x]:
    return (x, w[x])
  else:
    k = find(U[x], U, r, w)
    
    w[x] += w[U[x]]
    U[x] = k[0]
    
    return (U[x],w[x])

def merge(a, b, U, r, w, w_add): 
  a = find(a, U, r, w)[0]
  b = find(b, U, r, w)[0]
  if a == b:
    return  
  """
  if r[a] < r[b]:
    a, b = b, a 
  U[b] = a  
  if r[a] == r[b]:
    r[a] += 1
  """
  U[b] = a
  r[a] = max(r[a], r[b]+1)
  w[b] += w_add
  return

N, M = map(int,input().split())
U = [i for i in range(N)]
w = [0 for _ in range(N)]
r = [0 for _ in range(N)]

ans = True
for _ in range(M):
  
  L, R, D = map(int,input().split())
  L -= 1
  R -= 1
  t1 = find(L, U, r, w)
  t2 = find(R, U, r, w)
  
  if t1[0] == t2[0] and not(t2[1] - t1[1] == D):
    ans = False 
    break
  if not(t1[0] == t2[0]):
    D -= t2[1] - t1[1]
    if r[L] < r[R]:
      L, R = R, L
      D = -D
    merge(L, R, U, r, w, D)
  
print("Yes" if ans else "No")

Solution (Python):
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    q = deque([])
    visited = set()
    inf = 10 ** 10
    dist = [-inf] * (n + 1)

    for i in range(m):
        a, b, k = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k


    def dfs(u):
        q.append(u)
        while q:
            v = q.pop()
            visited.add(v)
            for x in g[v]:
                if x not in visited:
                    if ref[(v, x)] != []:
                        y = ref.get((v, x))
                        if dist[x] == -inf:
                            dist[x] = dist[v] + y
                        elif dist[x] != dist[v] + y:
                            print("No")
                            exit()
                    else:
                        y = ref.get((x, v))
                        if dist[x] == -inf:
                            dist[x] = dist[v] - y
                        elif dist[v] != dist[x] + y:
                            print("No")
                            exit()
                    q.append(x)


    for i in range(1, n + 1):
        if i not in visited:
            dist[i] = 1
            dfs(i)
    print("Yes")
if __name__ == '__main__':
    main()

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

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


    def unite(self, x, y, w):
        rx = self.root(x)
        ry = self.root(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.root(x) == self.root(y)

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


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

print('Yes')

Solution (Python):


from collections import deque

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

graph = {i: {} for i in range(1, n + 1)}


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = -c



distance = ["inf" for i in range(n + 1)]


visited = [False for i in range(n + 1)]
visited[0] = True


def find(x):
    d = deque()
    visited[x] = True
    distance[x] = 0
    d.append(x)
    flag = True
    while d and flag:

        x = d.popleft()
        for node in graph[x]:
            if visited[node] == False:
                visited[node] = True
                d.append(node)
                if distance[node] == "inf":
                    distance[node] = distance[x] + graph[x][node]
                else:
                    if  distance[node] != distance[x] + graph[x][node]:
                        flag = False
                        break
            elif visited[node]==True:
                if distance[node]!=distance[x]+graph[x][node]:
                    flag=False
                    break
         
    if flag:
        return False
    else:
        return True

all_flag = True
not_visited = True
while not_visited and all_flag:
    judge = False
    for i in range(1, n + 1):
        if visited[i] == False:
            judge = True
            if find(i):
                all_flag = False
                break
            else:
                pass

    if not judge:
        not_visited = False

if all_flag:
    print("Yes")

else:
    print("No")

Solution (Python):


from collections import deque

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

graph = {i: {} for i in range(1, n + 1)}


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = -c



distance = ["inf" for i in range(n + 1)]


visited = [False for i in range(n + 1)]
visited[0] = True


def find(x):
    d = deque()
    visited[x] = True
    distance[x] = 0
    d.append(x)
    flag = True
    while d and flag:

        x = d.popleft()
        for node in graph[x]:
            if visited[node] == False:
                visited[node] = True
                d.append(node)
                if distance[node] == "inf":
                    distance[node] = distance[x] + graph[x][node]
                else:
                    if  distance[node] != distance[x] + graph[x][node]:
                        flag = False
                        break
            elif visited[node]==True:
                if distance[node]!=distance[x]+graph[x][node]:
                    flag=False
                    break
         
    if flag:
        return False
    else:
        return True

all_flag = True
not_visited = True
while not_visited and all_flag:
    judge = False
    for i in range(1, n + 1):
        if visited[i] == False:
            judge = True
            if find(i):
                all_flag = False
                break
            else:
                pass

    if not judge:
        not_visited = False

if all_flag:
    print("Yes")

else:
    print("No")

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            p = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[p]
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dist[x]-self.dist[y] != d:
                print("No")
                exit()
        else:
            diff = self.dist[y]+d-self.dist[x]
            if diff>=0:
                self.parents[xRoot] = yRoot
                self.dist[xRoot] += diff
                self.find(x)
            else:
                self.parents[yRoot] = xRoot
                self.dist[yRoot] += abs(diff)
                self.find(y)
N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    L,R,D = map(int,input().split())
    tree.unite(L,R,D)
print("Yes")

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    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)

    n, m = map(int, input().split())
    
    par = [-1] * n
    wei = [0] * n
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if same(l, r):
            if diff(l, r) != d:
                print('No')
                sys.exit()
        else:
            unite(l, r, d)
    print('Yes')
    
if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  
        self.rank = [0]*(n+1)
        self.diff_weight = [0]*(n+1)  
    def root(self,x):  
        if self.par[x] == x:
            return x
        else:
            r = self.root(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]
    def same_check(self,x,y):  
        return self.root(x) == self.root(y)
    def weight(self,x):
        r = self.root(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.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = w

import sys

sys.setrecursionlimit(10**7)
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
G = UnionFind(N)
for i in range(M):
    L,R,D = LI()
    if G.same_check(L,R):
        if G.diff(L,R) != D:
            print('No')
            exit()
    else:
        G.unite(L,R,D)

print('Yes')

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

def bfs(s):
    que = deque([(0, s)])
    while que:
        d, v = que.popleft()
        if visited[v]:
            if d != dist[v]:
                return False
            continue
        visited[v] = True
        dist[v] = d
        for w, u in A[v]:
            que.append((d + w, u))
    return True

N, M = map(int, input().split())
A = [[] for _ in range(N)]
for _ in range(M):
    l, r, w = map(int, input().split())
    l -= 1
    r -= 1
    A[l].append((w, r))
    A[r].append((-w, l))
visited = [0] * N
dist = [0] * N
res = 'Yes'
for i in range(N):
    if visited[i]:
        continue
    f = bfs(i)
    if not f:
        res = 'No'
print(res)

Solution (Python):
import sys

sys.setrecursionlimit(4100000)

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')

Solution (Python):
"""
unite時に矛盾しないかどうかを判定させる。
同じ木の中では、より右にいるノードを親とする。
親との距離をどこかに記録しておく。
"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dict = [0]*(N+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.find(self.parents[x])
            u = self.dict[self.parents[x]]
            self.parents[x]=self.find(self.parents[x])
            
            self.dict[x] += u
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dict[x]-self.dict[y]!=d:
                print("No")
                exit()
        
        if self.dict[y]+d > self.dict[x]:
            self.parents[xRoot] = yRoot
            self.dict[xRoot] = self.dict[y]+d-self.dict[x]
        else:
            self.parents[yRoot] = xRoot
            self.dict[yRoot] = self.dict[x]-(self.dict[y]+d)

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Solution (Python):
from collections import deque

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

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

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")

Solution (Python):
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res += self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            self.par[xo] = x
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True

N, M = map(int, readline().split())
T = UFP(N)
ans = 'No'
for _ in range(M):
    l, r, d = map(int, readline().split())
    l -= 1
    r -= 1
    if not T.union(l, r, d):
        break
else:
    ans = 'Yes'
print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)
    self.weight = [0] * (N+1)

  def union(self, f, t, w):
    w += self.weight[f]
    w -= self.weight[t]

    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
      w = -w
    self.parents[p1] += self.parents[p2]
    self.weight[p2] = w
    self.parents[p2] = p1

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

  def compare_weight(self, x, y):
    self.find(x); self.find(y)
    return abs(self.weight[y] - self.weight[x])

  def same(self, n1, n2):
    
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
uf = UF(N)
flg = True
for _ in range(M):
  l,r,d = map(int, input().split())
  if uf.same(l, r):
    if uf.compare_weight(l,r) != d:
      flg = False
      break
  else:
    uf.union(l,r,d)

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

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            a = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[a]
            return self.parents[x]
    def unite(self,l,r,d):
        rRoot = self.find(r)
        lRoot = self.find(l)
        if rRoot == lRoot:
            if self.dist[l] - self.dist[r] != d:
                print("No")
                exit()
        else:
            
            newLDist = d + self.dist[r]
            if newLDist>=self.dist[l]:
                self.parents[lRoot] = rRoot
                self.dist[lRoot] = newLDist-self.dist[l]
            else:
                self.parents[rRoot] = lRoot
                self.dist[rRoot] = self.dist[l]-newLDist

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")