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
def input(): return sys.stdin.readline().strip()


class WeightedUnionFind():
    """
    https://qiita.com/drken/items/cce6fc5c579051e64fab
    UnionFindTreeに親ノードへ向かう辺の重みを追加したもの。
    これによりノードx, yがpath-connectedな場合にその間の符号付き距離をO(logN)で取得できる。
    ただしこれは「有向辺」であることに注意。
    というのも距離の導出は各ノードから根ノードまでの距離を取ってその差分で求めているため、
    無向辺の場合はLCAを求めないといけない。そしてUnionFindでは経路圧縮のせいでLCAを求めるのは不可能。
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する。
        parentsは各ノードの属する木の根を表す。
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する。
        diff_weightは各ノードから親ノードへ向かう辺の重みを格納する。
        根ノードに格納する重みは0とする。
        """
        self.n = n
        self.parents = [-1] * n
        self.diff_weight = [0] * n

    def find(self, x):
        """
        xの属する木の根を返す。
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す。
        """
        if self.parents[x] < 0:
            return x
        else:
            edge_weight = self.diff_weight[x]
            prev_parent = self.parents[x]
            self.parents[x] = self.find(self.parents[x])
            self.diff_weight[x] = self.diff_weight[prev_parent] + edge_weight
            return self.parents[x]

    def union(self, x, y, w):
        """
        xからyへ重みwの辺を繋ぐ。
        既にx, yがpath-connectedな場合はFalseを返す。
        そうでなければTrueを返す。
        """
        rx = self.find(x)
        ry = self.find(y)
        w += self.diff_weight[y] - self.diff_weight[x]
        w *= -1 

        if rx == ry:
            return False

        if self.parents[rx] > self.parents[ry]:
            rx, ry = ry, rx 
            w *= -1 

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.diff_weight[ry] = w
        return True

    def weight(self, x):
        """
        xからxの属する木の根ノードまでの重みを求める
        """
        _ = self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """
        xからyへ向かうのにかかる重みを求める
        """
        return self.weight(x) - self.weight(y)

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    tree = WeightedUnionFind(N)
    for _ in range(M):
        l, r, d = map(int, input().split())
        l, r = l-1, r-1
        if tree.same(l, r):
            dist = tree.diff(l, r)
            if d != dist:
                print("No")
                return
        else:
            tree.union(l, r, d)
    print("Yes")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
q = deque([])
visited = set()
dist = [None] * (n + 1)

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

def dfs(u):
    q.append(u)
    while q:
        v = q.pop()
        visited.add(v)
        for x, d in g[v]:
            if x not in visited:
                if dist[x] is None:
                    dist[x] = dist[v] + d
                elif dist[x] != dist[v] + d:
                    return False
                q.append(x)
    return True

for i in range(1, n + 1):
    if i not in visited:
        dist[i] = 1
        if not dfs(i):
            print("No")
            exit()
print("Yes")

Solution (Python):
n, m = (int(x) for x in input().split())
LRD = [tuple(int(x) for x in input().split()) for _ in range(m)]

G = [[] for _ in range(n)]
dist = dict()
for l, r, d in LRD:
    l -= 1
    r -= 1
    G[l].append(r)
    G[r].append(l)
    dist[(l, r)] = d
    dist[(r, l)] = -d

INF = 10**18
X = [INF] * n
for i in range(n):
    stack = [i]
    while stack:
        u = stack.pop()
        if X[u] == INF:
            X[u] = 0
        for v in G[u]:  
            if X[v] == INF:
                X[v] = X[u] + dist[(u, v)]
                stack.append(v)
            else:
                if X[v] != X[u] + dist[(u, v)]:
                    print("No")
                    exit()

print("Yes")

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):
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 and dist[v] == -inf:
                            continue
                        elif dist[x] == -inf:
                            dist[x] = dist[v] + y
                        elif dist[v] == -inf:
                            dist[v] = dist[x] - y
                        elif dist[x] != dist[v] + y:
                            
                            print("No")
                            exit()
                    else:
                        y = ref.get((x, v))
                        if dist[x] == -inf and dist[v] == -inf:
                            continue
                        elif dist[v] == -inf:
                            dist[v] = dist[x] + y
                        elif 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):
import sys
from collections import deque
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  tree = [[] for _ in range(n)]
  for i in range(m):
    l, r, d = map(int, input().split())
    tree[l-1].append((r-1, d))
    tree[r-1].append((l-1, -d))
  
  ans = [0]*n
  not_yet = deque([])
  already = [False]*n
  judge = True
  
  for i in range(n):
    if already[i]:
      continue
    already[i] = True
    for v in tree[i]:
      index, dist = v[0], v[1]
      ans[index] = dist
      already[index] = True
      not_yet.append(index)
    while not_yet:
      index = not_yet.popleft()
      for v in tree[index]:
        index2, dist = v[0], v[1]
        if already[index2]:
          if ans[index] + dist != ans[index2]:
            judge = False
        else:
          already[index2] = True
          ans[index2] = ans[index] + dist
          not_yet.append(index2)
          
  print("Yes" if judge else "No")
  
if __name__ == "__main__":
  main()

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**9
eps = 10**-7

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


par = [i for i in range(N+1)]

rank = [0]*(N+1)




def root(x):
    if par[x] == x:             
        return x
    else:
        par[x] = root(par[x])   
        return par[x]


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        
    else:
        par[y] = x              
        
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
print('Yes')

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**9
eps = 10**-7

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


par = [i for i in range(N+1)]

rank = [0]*(N+1)




def root(x):
    if par[x] == x:             
        return x
    else:
        par[x] = root(par[x])   
        return par[x]


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        
    else:
        par[y] = x              
        
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
print('Yes')

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**9
eps = 10**-7

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


par = [i for i in range(N+1)]

rank = [0]*(N+1)




def root(x):
    if par[x] == x:             
        return x
    else:
        par[x] = root(par[x])   
        return par[x]


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        
    else:
        par[y] = x              
        
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
print('Yes')

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**9
eps = 10**-7

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


par = [i for i in range(N+1)]

rank = [0]*(N+1)




def root(x):
    if par[x] == x:             
        return x
    else:
        par[x] = root(par[x])   
        return par[x]


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        
    else:
        par[y] = x              
        
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
    if max(x.values()) - min(x.values()) > 10**9:
        print('No')
        exit()
print('Yes')

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=MI()
wuf=WeightedUnionfind(n)
for i in range(m):
    l,r,d=MI()
    
    
    if wuf.same(l,r):
        
        if wuf.diff(l,r)!=d:
            print("No")
            sys.exit()
    else:
        wuf.union(l,r,d)
print("Yes")

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=MI()
wuf=WeightedUnionfind(n)
for i in range(m):
    l,r,d=MI()
    
    
    if wuf.same(l,r):
        
        if wuf.diff(l,r)!=d:
            print("No")
            sys.exit()
    else:
        wuf.union(l,r,d)
print("Yes")

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

q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
  x = q.popleft()
  if pos[x] == None:
    pos[x] = 0
  for y,d in graph[x]:
    if pos[y] == None:
      pos[y] = pos[x] + d
      q.appendleft(y)
      continue
    if pos[y] != pos[x] + d:
      print("No")
      exit()

print("Yes")

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N,M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    a, b, c = getNM()
    dist[a - 1].append((b - 1, c))
    dist[b - 1].append((a - 1, -c))

pos = deque([i for i in range(N)])
point = [float('inf')] * N

while len(pos) > 0:
    now = pos.popleft()
    if point[now] == float('inf'):
        point[now] = 0
    for next, dis in dist[now]:
        if point[next] == float('inf'):
            point[next] = point[now] + dis
            pos.appendleft(next)
            continue
        if point[next] != point[now] + dis:
            print("No")
            exit()

print("Yes")

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N,M = getNM()
graph = [[] for i in range(N)]
for _ in range(M):
  l,r,d = getNM()
  graph[l-1].append((r-1,d))
  graph[r-1].append((l-1,-d))

q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
  x = q.popleft()
  if pos[x] == None:
    pos[x] = 0
  for y,d in graph[x]:
    if pos[y] == None:
      pos[y] = pos[x] + d
      q.appendleft(y)
      continue
    if pos[y] != pos[x] + d:
      print("No")
      exit()

print("Yes")

Solution (Python):

















import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """
    
    from collections import deque
    
    
    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))
    
    seen = [False]*N
    ans = [0]*N
    
    
    def dfs(G, v):
    
        
    
        seen[v] = True
        stack = deque([v])
        while stack:
            v = stack.pop()
            for next_v,cost in G[v]:
                if not seen[next_v]:
                    ans[next_v] =ans[v]+cost
                else:
                    if ans[next_v] !=ans[v]+cost:
                        return 'No'
                    else: continue

                seen[next_v] = True
                stack.append(next_v)
    
    
    def main():
        for i in range(N):
            if not seen[i]:
                if dfs(G,i)=='No':
                    return 'No'
                    break
                else:
                    continue
        return 'Yes'
    print(main())
    
    
resolve()

Solution (Python):
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  edge[l].append((r,d))
  edge[r].append((l,-d))
ans=[10**20]*n
inf=10**20
for i in range(n):
  if ans[i]!=inf:continue
  stack=[i]
  visited={i}
  ans[i]=0
  for node in stack:
    for mode,d in edge[node]:
      if ans[node]+d!=ans[mode]!=inf:exit(print("No")) 
      if mode in visited:continue
      visited.add(mode)
      stack.append(mode)
      if ans[mode]==inf:
        ans[mode]=ans[node]+d
        
print("Yes")

Solution (Python):
from collections import deque

def dfs(s):
    stack = deque([s])
    dist[s] = 0
    while stack:
        v = stack.pop()
        for d, u in E[v]:
            if dist[u] is None:
                dist[u] = dist[v] + d
                stack.append(u)
            else:
                if dist[u] != dist[v] + d:
                    return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l-1].append((d, r - 1))
    E[r-1].append((-d, l - 1))
dist = [None] * N
for i in range(N):
    if dist[i] is not None:
        continue
    if not dfs(i):
        print('No')
        break
else:
    print('Yes')

Solution (Python):
n, m = map(int, input().split())
vertices = {i: [] for i in range(n)}
for _ in range(m):
    l, r, d = map(int, input().split())
    vertices[l - 1].append((r - 1, d))
    vertices[r - 1].append((l - 1, -d))


def answer():
    x = [None] * n

    for i in range(n):
        if x[i] is not None:
            continue
        x[i] = 0
        queue = [i]

        while queue:
            i0 = queue.pop()
            for i1, d in vertices[i0]:
                
                if x[i1] is None:
                    x[i1] = x[i0] + d
                    queue.append(i1)
                elif x[i1] != x[i0] + d:
                    return False

    return True


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

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

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

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

"""

flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf: 
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')
"""


dist = [inf]*n
def dfs(i, totald = 0):
    if dist[i] < inf:
        if dist[i] == totald:
            return True
        else:
            return False
    dist[i] = totald
    for e in edge[i]:
        nnode, d = e
        if not dfs(nnode, totald+d):
            return False
    return True


f = True
for i in range(n):
    if dist[i] == inf:
        if not dfs(i, 0):
            f = False
            break
if f:
    print('Yes')
else:
    print('No')

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

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

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

flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf:
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')

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

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

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[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.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        
        else:
            self.parents[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]

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

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()