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):
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

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


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Solution (Python):
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

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


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append((x,0))
        while q:
            now,cnt = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = cnt+d
                    q.append((nex,cnt+d))
                else:
                    if dis[nex] != cnt+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

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

    from collections import deque
    
    inf = 10**18
    dist = [inf]*n

    for i in range(n):
        if dist[i] != inf:
            continue
        dist[i] = 0
        q = deque()
        q.append([i,0])
        while q:
            now,cnt = q.popleft()
            for nxt,nd in lines[now]:
                if dist[nxt] == inf:
                    dist[nxt] = cnt+nd
                    q.append([nxt,cnt+nd])
                    continue
                if dist[nxt] != cnt+nd:
                    print('No')
                    return 0
    print('Yes')

if __name__ == '__main__':
    main()

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]
import sys
n,m=map(int,input().split())
lrd=[]
tree = WeightedUnionFindTree(n)
for _ in range(m):
    lrd.append(list(map(int,input().split())))
for l,r,d in lrd:
    tree.unite(l-1,r-1,d)
    
for l,r,d in lrd:
    if tree.is_same(l-1,r-1):    
        if tree.diff(l-1,r-1) != d:
            print("No")
            sys.exit()
    else:
        tree.unite(l-1,r-1,d)
else:
    print("Yes")

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,z
    r,d = find(g[x][0],g[x][1])
    g[x] = [r,d]
    return g[x][0],g[x][1]+z

def union(x,y,d):
    if g_num[g[x][0]] < g_num[g[y][0]]:
        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d - g[y][1]
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,0)[0] == find(r,0)[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Solution (Python):






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

INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  
  q.append([i,-1])
  while q:
    v,parent = q.popleft()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Solution (Python):






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

INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  
  q.append([i,-1])
  while q:
    v,parent = q.pop()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Solution (Python):






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

INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  
  q.append([i,-1])
  while q:
    v,parent = q.popleft()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Solution (Python):






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

INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

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

from collections import defaultdict
G = defaultdict(list)

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


pos = [float("inf") for _ in range(n)]
for i in range(n):
    if pos[i] == float("inf"):
        stack = [i]
        pos[i] = 0
    while stack:
        p = stack.pop()
        for a, d in G[p]:
            if pos[a] == float("inf"):
                pos[a] = pos[p] + d
                stack.append(a)

for i in range(n):
    for to, d in G[i]:
        if pos[to] - pos[i] != d:
            print("No")
            exit()

print("Yes")

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

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

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


position = [10**10]*n
for i in range(n):
    if position[i]==10**10:
        stack = [i]
        position[i] = 0
        while stack:
            p = stack.pop()
            for to,d in dist[p]:
                if position[to]==10**10:
                    position[to]=position[p]+d
                    stack.append(to)

for i in range(n):
    for to,d in dist[i]:
        if position[to]-position[i]!=d:
            print('No')
            exit()
print('Yes')

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

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

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

def BFD(x):
  global checked,answer,graph
  checked[x]=1
  for i,distance in graph[x]:
    if answer[i]=="first":
      answer[i]=answer[x]+distance
    else:
      if answer[i]!=answer[x]+distance:
        print("No")
        exit()
    
    if checked[i]==0:
      BFD(i)

checked=[0]*N
answer=["first"]*N

for i in range(N):
  if checked[i]==0:
    answer[i]=0
    BFD(i)

print("Yes")

Solution (Python):
import sys
import collections

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    LRD = [[int(x) for x in input().split()] for _ in range(M)]
    A = [[] for j in range(N + 1)]

    if M == 0:
        print("Yes")
        return

    slist = set()
    for l, r, d in LRD:
        A[l].append([r, d])
        A[r].append([l, -d])
        slist.add(l)
        slist.add(r)

    dmemo = [None] * (N + 1)

    f = False
    for i in list(slist):
        if dmemo[i] is not None:
            continue
        s = collections.deque()
        s.append(i)
        dmemo[i] = 0

        while s:
            c = s.pop()
            for r, d in A[c]:
                if dmemo[r] is not None:
                    if dmemo[r] - dmemo[c] != d:
                        f = True
                        break
                else:
                    dmemo[r] = dmemo[c] + d
                    s.append(r)
            if f:
                break
        if f:
            break

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


if __name__ == '__main__':
    main()

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

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

lrd=[[] for _ in range(n)]

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

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    
    for llrrdd in lrd[x]:
        
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")

Solution (Python):
from sys import stdin


def main():
    from collections import deque

    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = deque([])
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  
            L_R_D_arr.append(_)
        
        iter_ = [float('inf')]*(N+1)
        iter_[L_R_D_arr[0][0]] = 0

        TF = 'No'
        rot_cnt = 0
        while len(L_R_D_arr)>0:
            if rot_cnt > len(L_R_D_arr):
                iter_ = [float('inf')]*(N+1)
                iter_[L_R_D_arr[0][0]] = 0
            else:
                L, R, D = L_R_D_arr[0]
                if iter_[L] == float('inf'):
                    if iter_[R] == float('inf'):
                        L_R_D_arr.rotate(-1)
                        rot_cnt += 1
                    else:
                        iter_[L] = iter_[R]-D
                        L_R_D_arr.popleft()
                        rot_cnt = 0
                else:
                    rot_cnt = 0
                    if iter_[R] == float('inf'):
                        iter_[R] = iter_[L]+D
                        L_R_D_arr.popleft()
                    elif iter_[R] == iter_[L]+D:
                        L_R_D_arr.popleft()
                    else:
                        break
        else:
            TF = 'Yes'
        
    print(TF)



class Weighted_Union_Find():
    def __init__(self, N=1, SUM_UNITY=0):
        self.par  = [i for i in range(N)]  
        self.rank = [0] * N                
        self.diff_weight = [SUM_UNITY] * N 
    
    
    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 r

    
    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    
    def merge(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: 
            return False
        else:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
                w = -w
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.diff_weight[y] = w
            return True

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


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  
            L_R_D_arr.append(_)
        
        TF = 'No'
        wuf = Weighted_Union_Find(N)
        for L,R,D in L_R_D_arr:
            L -= 1
            R -= 1
            if wuf.issame(L,R):
                diff = wuf.diff(L,R)
                if diff != D:
                    break
            else:
                wuf.merge(L,R,D)
        else:
            TF = 'Yes'
        
    print(TF)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
g = [[] for _ in range(n)]
for i in range(m):
    l,r,d = inpl()
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
seen = [False] * n
dist = [0] * n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    while q:
        now = q.popleft()
        seen[i] = True
        for v,d in g[now]:
            if seen[v]:
                if dist[v] != d + dist[now] :
                    print('No')
                    quit()
            else:
                dist[v] = dist[now] + d
                seen[v] = True
                q.append(v)
print('Yes')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

        
        self.weights = [0] * n_nodes

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
            w *= -1

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weights[y] = w
        return

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

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

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_parent_list(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    tree = WeightedUnionFind(N)
    flag = True
    for _ in range(M):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if not tree.is_same(l, r):
            tree.unite(l, r, d)
        else:
            if tree.get_weight(l, r) == d:
                continue
            else:
                flag = False

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


if __name__ == "__main__":
    main()

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

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

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

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


    MIN = -10 ** 18

    lst = [MIN] * (N + 1)

    que = deque()
    que_append = que.append
    que_popleft = que.popleft

    for i in range(1, N + 1):
        if lst[i] == MIN:
            que_append(i)
            lst[i] = 0

        while que:
            tmp = que_popleft()
            for next_, d in G[tmp]:
                if lst[next_] == MIN:
                    lst[next_] = lst[tmp] + d
                    que_append(next_)
                    continue
                
                if lst[next_] == lst[tmp] + d:
                    continue
                else:
                    print ('No')
                    exit()

    print ('Yes')

if __name__ == '__main__':
    main()

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

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

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

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()
que_append = que.append
que_popleft = que.popleft

for i in range(1, N + 1):
    if lst[i] == MIN:
        que_append(i)
        lst[i] = 0

    while que:
        tmp = que_popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que_append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                print ('No')
                exit()

print ('Yes')

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

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

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

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()

for i in range(1, N + 1):
    if lst[i] == MIN:
        que.append(i)
        lst[i] = 0

    while que:
        tmp = que.popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que.append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                print ('No')
                exit()

print ('Yes')

Solution (Python):
from collections import deque

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

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

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()

for i in range(1, N + 1):
    if lst[i] == MIN:
        que.append(i)
        lst[i] = 0

    while que:
        tmp = que.popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que.append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                print ('No')
                exit()

print ('Yes')

Solution (Python):
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline
INF = float("inf")


def check(g, n):
    visited = [False] * n
    dist = [INF] * n  
    
    for s in range(n):
        if visited[s]:
            continue
        
        que = deque([(0, s)])
        dist[s] = 0
        visited[s] = True
        while que:
            d, u = que.popleft()
            for nd, v in g[u]:
                nd += d
                if visited[v]:
                    
                    if dist[v] != nd:
                        return False
                else:
                    
                    visited[v] = True
                    dist[v] = nd
                    que.append((nd, v))
    return True


def main():
    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((d, r))  
        g[r].append((-d, l))  
    if check(g, n):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

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

dist=[None]*n
from collections import deque

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

Solution (Python):
class WeightedUnionFind:
    """ あっとさんありがとうございます """

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

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

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

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

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


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    uf = WeightedUnionFind(N)
    LRD = [[int(i) for i in input().split()] for j in range(M)]
    for le, ri, d in LRD:
        if uf.same(le, ri):
            if uf.diff(le, ri) != d:
                return print("No")
        uf.union(le, ri, d)
    print("Yes")


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    G=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int, input().split())
        l,r=l-1,r-1
        G[l].append((r,d))
        G[r].append((l,-d))

    d=[0]*N
    used=[False]*N
    ans=True
    for i in range(N):
        if used[i]: continue
        used[i]=True
        stk=[(i,0)]
        while stk:
            v,vd=stk.pop()
            for to,td in G[v]:
                if used[to]:
                    if d[to]!=vd+td:
                        ans=False
                    continue
                used[to]=True
                d[to]=vd+td
                stk.append((to,d[to]))
    print('Yes' if ans else 'No')

if __name__ == '__main__':
    main()

Solution (Python):
def Find(x, par, diff_weight):
    if par[x] < 0:
        return x
    else:
        px = Find(par[x], par, diff_weight)
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px

def Unite(x, y, par, rank, diff_weight, w):
    w += diff_weight[x] - diff_weight[y]
    x = Find(x, par, diff_weight)
    y = Find(y, par, diff_weight)

    if x != y:
        if rank[x] < rank[y]:
            x, y =  y, x
            w = -w
        if rank[x] == rank[y]:
            rank[x] += 1
        par[x] += par[y]
        par[y] = x
        diff_weight[y] = w

def Same(x, y, par, diff_weight):
    return Find(x, par,diff_weight) == Find(y, par, diff_weight)

def Size(x, par, diff_weight):
    return -par[Find(x, par, diff_weight)]

def Weight(x, par, diff_weight):
    Find(x, par, diff_weight)
    return diff_weight[x]

def Diff(x, y, par, diff_weight):
    return Weight(y, par, diff_weight)  - Weight(x, par, diff_weight)

import sys
input = sys.stdin.buffer.readline
n, m = map(int, input().split())

par = [-1]*n
rank = [0]*n
diff_weight = [0]*n

for i in range(m):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if not Same(l, r, par, diff_weight):
        Unite(l, r, par, rank, diff_weight, d)
    else:
        if Diff(l, r, par, diff_weight) != d:
            print('No')
            exit()
else:
    print('Yes')

Solution (Python):
n,m=map(int,input().split())
ans=[10**10]*n
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))
for i in range(n):
  if ans[i]==10**10:
    ans[i]=0
    Q=[i]
    while Q:
      P=[]
      for j in Q:
        for k,d in edge[j]:
          if ans[k]==10**10:
            ans[k]=ans[j]+d
            P.append(k)
          elif ans[j]+d!=ans[k]:
            print("No");exit()
      Q=P
print("Yes")

Solution (Python):
n,m=map(int,input().split())
ans=[10**10]*n
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))
for i in range(n):
  if ans[i]==10**10:
    ans[i]=0
    Q=[i]
    while Q:
      P=[]
      for j in Q:
        for k,d in edge[j]:
          if ans[k]==10**10:
            ans[k]=ans[j]+d
            P.append(k)
          elif ans[j]+d!=ans[k]:
            print("No");exit()
      Q=P
print("Yes")

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to, dist = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, dist))
    edges[to].append((fr, -dist))

def isOk():
    visited = [False] * N
    INF = 10**18
    minDist = [INF] * N
    for s in range(N):
        if visited[s]:
            continue
        st = [(s, 0)]
        minDist[s] = 0
        visited[s] = True
        while st:
            now, dist = st.pop()

            for to, d in edges[now]:
                d += dist
                if visited[to]:
                    if minDist[to] != d:
                        return False
                else:
                    visited[to] = True
                    minDist[to] = d
                    st.append((to, d))
    return True

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