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
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

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

def bfs(graph, start):
    while graph != {}:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0
        while queue:
            u = queue.popleft()
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    if v in graph:
                        queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            
    return True

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

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

Solution (Python):
class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  
        self.rank = [0] * n_nodes  
        self.weights = [0] * n_nodes

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

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

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


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

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if not uft.is_same(l, r):
        uft.unite(l, r, d)
    else:
        if uft.diff(l, r) != d:
            print("No")
            quit()
else:
    print("Yes")

Solution (Python):
class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  
        self.rank = [0] * n_nodes  
        self.weights = [0] * n_nodes

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

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

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


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

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if not uft.is_same(l, r):
        uft.unite(l, r, d)
    else:
        if uft.diff(l, r) != d:
            print("No")
            quit()
else:
    print("Yes")

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


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


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

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')

Solution (Python):
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)
for i 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:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

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

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

seen = ['!'] * (N+1)
for i in range(1, N+1):
    if seen[i] == '!':
        que = deque()
        seen[i] = 0
        que.append(i)
        while que:
            v = que.popleft()
            for u, d in adj[v]:
                if seen[u] == '!':
                    seen[u] = seen[v] + d
                    que.append(u)
                else:
                    if seen[v] + d != seen[u]:
                        print('No')
                        exit()
print('Yes')

Solution (Python):
class UnionFind():
    
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
uni = UnionFind(N)
for _ in range(M):
    a, b, d = map(int, input().split())
    uni.Unite(a-1, b-1)
    graph[a-1].append((d, b-1))
    graph[b-1].append((-d, a-1))

INF = 10**14
A = [INF]*N
def bfs(start):
    q = [start]
    A[start] = 0
    while q:
        qq = []
        for p in q:
            for d, np in graph[p]:
                if A[np] == INF:
                    A[np] = A[p] + d
                    qq.append(np)
                elif A[np] != A[p]+d:
                    return False
        q = qq
    return True

root = set()
for i in range(N):
    root.add(uni.Find_Root(i))

ok = True
for r in root:
    ok = ok and bfs(r)

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

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 False
        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.diff_weight[y] = w
            self.rank[x] += 1
        return True

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')
            break
    wuf.unite(l, r, d)
else:
    print('Yes')

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


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

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

    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 diff_w(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    a = []
    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)
        a.append(l)
        a.append(r)

    for i in set(a):
        D.find(i)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()

    print('Yes')


main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


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

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

    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 diff_w(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.find(l)
        D.find(r)
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()

    print('Yes')


main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


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

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

    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_w(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in range(N):
        D.find(i)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()
    
    print('Yes')


main()

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):
        """ x 根に対する重みを返す """
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """ x と y の差分をとる """
        return self.weight(y) - self.weight(x)

    def unite(self, x, y, w):
        """ ノード 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')
            break
    else:
        wuf.unite(l, r, d)
else:
    print('Yes')

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

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

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

    
    def unite(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            
            if self.parents[x] > self.parents[y]:
                x, y = y, x
                w = -w
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.weight[y] = w
            return True

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

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

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


    


def main():
    N, M = map(int, input().split())
    uni = WeightUnionFind(N)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        if uni.same(L, R):
            if D != uni.diff(L, R):
                print('No')
                exit()
        else:
            uni.unite(L,R,D)

    print('Yes')
    


if __name__ == "__main__":
    main()

Solution (Python):
import sys
n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for i in range(m)]
x=["a"]*(n+1)

R=[[] for i in range(n+1)]
L=[[] for i in range(n+1)]
for u in lrd:
    l,r,d=u
    R[l].append([r,d])
    L[r].append([l,d])
for i in range(1,n+1):
    if x[i]=="a":
        x[i]=0
        que=[i]
        while que:
            h=que.pop()
            for u in R[h]:
                r,d=u
                if x[r]=="a":
                    x[r]=x[h]+d
                    que.append(r)
                else:
                    if x[r]==x[h]+d:
                        continue
                    else:
                        print("No")
                        sys.exit()
            for u in L[h]:
                l,d=u
                if x[l]=="a":
                    x[l]=x[h]-d
                    que.append(l)
                else:
                    if x[l]==x[h]-d:
                        continue
                    else:
                        print("No")
                        sys.exit()
print("Yes")

Solution (Python):
def resolve():

    N,M = map(int,input().split())
    root = list(range(N))
    depth = [1 for _ in range(N)]
    dist = [0 for _ in range(N)]

    def find(a,root,dist):
        if root[a] == a:
            return (a,0)
        else:
            root[a],d = find(root[a],root,dist)
            dist[a] += d
            return(root[a],dist[a])

    def unite(a,b,d,root,depth,dist):
        A,dist_a = find(a,root,dist)
        B,dist_b = find(b,root,dist)
        if A == B:
            if dist_b - dist_a == d:
                return True
            else:
                return False
        else:
            if depth[A] > depth[B]:
                root[B] = A
                depth[A] += depth[B]
                dist[B] = dist_a - dist_b + d
            else:
                root[A] = B
                depth[B] += depth[A]
                dist[A] = dist_b - dist_a - d
            return True
        
    ans = True
    for _ in range(M):
        L,R,D = map(int,input().split())
        if not (unite(L-1,R-1,D,root,depth,dist)):
            ans = False
            break
    print("Yes" if ans else "No")
resolve()

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


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

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)
        self.size = [1] * (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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            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 size(self, x):
        x = self.find(x)
        return self.size(x)

    def diff(self, x, y):
        if self.same_check(x, y) == True:
            return self.weight[x] - self.weight[y]
        else:
            print("inf")


def main():
	N, M = getlist()
	judge = "Yes"
	UF = WeightedUnionFind(N)
	for i in range(M):
		L, R, D = getlist()
		if UF.same_check(L - 1, R - 1):
			if UF.diff(L - 1, R - 1) != D:
				judge = "No"
				break
		else:
			UF.union(L - 1, R - 1, D)
	print(judge)



if __name__ == '__main__':
	main()

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 i in range(m):
    a,b,c=map(int,input().split())
    if not uf.same(a,b):
        uf.union(a,b,c)
    else:
        if uf.diff(a,b)!=c:
            print('No')
            exit()
print('Yes')

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
    self.weight = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      r = self.Find_Root(self.root[x])
      self.weight[x] += self.weight[self.root[x]]
      self.root[x] = r
      return r
  def GetWeight(self, x):
    self.Find_Root(x)
    return self.weight[x]
  def Unite(self, x, y, w):
    w += self.GetWeight(x)
    w -= self.GetWeight(y)
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return False
    if self.rnk[x] < self.rnk[y]:
      x, y = y, x
      w = -w
    if self.rnk[x] == self.rnk[y]:
      self.rnk[x] += 1
    self.root[y] = x
    self.weight[y] = w
    return True
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
  def Diff(self, x, y):
    return self.GetWeight(y) - self.GetWeight(x)
  
def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


union = UnionFind(N-1)

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((d, b-1))
    graph[b-1].append((-d, a-1))
    union.Unite(a-1, b-1)

roots = set()
for i in range(N):
    roots.add(union.Find_Root(i))

NUM = [None for _ in range(N)]
checked = [False for _ in range(N)]

def dfs(p, NUM, ans):
    x = NUM[p]
    for d, q in graph[p]:
        
        if NUM[q] is None:
            NUM[q] = x+d
        elif NUM[q] != x+d:
            
            ans = False
            return ans
        if checked[q]:
            continue
        checked[q] = True
        ans = dfs(q, NUM, ans)
    return ans

ans = True
for r in roots:
    NUM[r] = 0
    ok = dfs(r, NUM, True)
    ans = ans and ok

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

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))
default = 100000000000000000000000

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

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

loc = 0
while loc < N:
	if dist[loc] == default:
		dist[loc] = 0
		que = deque([])
		que.append(loc)
		while len(que) > 0:
			node = que.popleft()
			if len(graph[node]) > 0:
				for edge in graph[node]:
					if dist[edge[0]] == default:
						dist[edge[0]] = dist[node] + edge[1]
						que.append(edge[0])
					elif dist[edge[0]] != dist[node] + edge[1]:
						print("No")
						exit()
	loc += 1
print("Yes")