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 numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

class Repeat (object):
	__slots__ = [
		'element',
		'times'
	]
	
	def __init__(self, element, times : int):
		self.element = element
		self.times = int(times)
	
	def __len__(self):
		return self.times
	
	def __iter__(self):
		return iter(self.element for _ in range(self.times))

def repeat(element, times : int):
	return Repeat(element, times)

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			abelian_operator=IntAddition()):
		self.parent = []
		self.potential = []
		self.op = abelian_operator
		
		self.extend(num_nodes)
	
	def append(self):
		self.parent.append(-1)
		self.potential.append(self.op.identity)
	
	def extend(self, num_nodes):
		self.parent.extend(repeat(-1, num_nodes))
		self.potential.extend(repeat(self.op.identity, num_nodes))
	
	def root(self, x):
		parent = self.parent[x]
		if 0 <= parent:
			self.parent[x] = self.root(parent)
			self.potential[x] = self.op.operate(
				self.potential[x], self.potential[parent]
			)
			x = self.parent[x]
		return x
	
	def difference_from_root_to(self, x):
		self.root(x)
		return self.potential[x]
		
	def size(self, x):
		return -self.parent[self.root(x)]
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None):
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.potential[x]
		y, py = self.root(y), self.potential[y]
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		if x == y:
			return difference == 0
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.potential[y] = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	if not uf.unite(L, R, D):
		valid = False

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

Solution (Python):
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

from itertools import repeat

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			abelian_operator=IntAddition()):
		self.parent = []
		self.potential = []
		self.op = abelian_operator
		
		self.extend(num_nodes)
	
	def append(self):
		self.parent.append(-1)
		self.potential.append(self.op.identity)
	
	def extend(self, num_nodes):
		self.parent.extend(repeat(-1, num_nodes))
		self.potential.extend(repeat(self.op.identity, num_nodes))
	
	def root(self, x):
		parent = self.parent[x]
		if 0 <= parent:
			self.parent[x] = self.root(parent)
			self.potential[x] = self.op.operate(
				self.potential[x], self.potential[parent]
			)
			x = self.parent[x]
		return x
	
	def difference_from_root_to(self, x):
		self.root(x)
		return self.potential[x]
		
	def size(self, x):
		return -self.parent[self.root(x)]
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None):
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.potential[x]
		y, py = self.root(y), self.potential[y]
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		if x == y:
			return difference == 0
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.potential[y] = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	if not uf.unite(L, R, D):
		valid = False

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

Solution (Python):
n,m=map(int,input().split())
lrd=[tuple(map(int,input().split())) for i in range(m)]

class WeightedUnionFind:
  def __init__(self,n):
    self.parent = [i for i in range(n)]
    self.rank = [0] * n
    self.count = 0
    self.weight = [0] * n
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      pa = self.root(self.parent[a])
      self.weight[a] += self.weight[self.parent[a]]
      self.parent[a] = pa
      return pa
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b,w):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self.rank[ra] < self.rank[rb]:
      self.parent[ra] = rb
      self.weight[ra] = w - self.weight[a] + self.weight[b]
    else:
      self.parent[rb] = ra
      self.weight[rb] = -w - self.weight[b] + self.weight[a]
      if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
    self.count += 1
  def diff(self,a,b):
    return self.weight[a] - self.weight[b]

uf=WeightedUnionFind(n)
for l,r,d in lrd:
  l,r=l-1,r-1
  if uf.is_same(l,r):
    if uf.diff(l,r)!=d:
      print('No')
      exit(0)
  else:
      uf.unite(l,r,d)
print('Yes')

Solution (Python):

def dijkstra(node, edge, check):
    """
    nodeを含む連結グラフの中で、
    矛盾が発生しないか確認する
    矛盾が発生しない場合、
    nodeを0としたときの各ノードのスコアを返す
    """
    
    d = dict()
    st = [(node, 0)]
    curr_min = float('inf')
    curr_max = -float('inf')
    while st:
        curr_node, curr_d = st.pop()
        
        if curr_node in d.keys():
            if d[curr_node] != curr_d:
                
                return None, None, None, check
            else:
                continue
        
        d[curr_node] = curr_d 
        check[curr_node] = True
        if curr_d < curr_min:
            curr_min = curr_d
        if curr_max < curr_d:
            curr_max = curr_d

        
        for nxt, diff in edge[curr_node]:
            st.append((nxt, curr_d + diff))
    
    return d, curr_min, curr_max, check


def submit():
    n, m = (int(e) for e in input().split())
    
    
    edge = {i : [] for i in range(1, n + 1)}
    for _ in range(m):
        l, r, d = (int(e) for e in input().split())
        edge[l].append((r, d))
        edge[r].append((l, -d))

    check = {i: False for i in range(1, n + 1)}
    curr_max = -float('inf')

    for i in range(1, n + 1):
        if not check[i]:
            d, sub_min, sub_max, check = dijkstra(i, edge, check)

            if d == None:
                print('No')
                return
            
            sub_max -= sub_min
            if sub_max > curr_max:
                curr_max = sub_max

    if curr_max > 10 ** 9:
        print('No')
    else:
        print('Yes')


submit()

Solution (Python):
import sys
n, m = map(int, input().split())
if m==0:
    print("Yes")
    sys.exit()

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

from collections import deque
INF = "INF"
visit = [INF for _i in range(n+1)]
for i in range(1, n+1):
    if visit[i]==INF:
        visit[i] = 0
    else:
        continue
    q = deque([i])
    while q:
        p = q.popleft()
        if visit[p]==INF:
            visit[p] = 0
        for i, j in tree[p]:
            if i==p:
                continue
            elif visit[i] == INF:
                visit[i] = visit[p]+j
                q.append(i)
            elif visit[i] == visit[p]+j:
                continue
            else:
                print("No")
                sys.exit()

print("Yes")

Solution (Python):


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

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def bfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    
    for s in range(N):
        if h[s]: continue  
        
        if not bfs(s):
            print('No')
            return

    
    for s in range(N):
        if ~dist[s]: continue
        if not bfs(s):
            print('No')
            return

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def dfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    
    for s in range(N):
        if h[s]: continue  
        
        if not dfs(s):
            print('No')
            return

    
    for s in range(N):
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def dfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    
    for s in range(N):
        if h[s]: continue  
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    
    for s in range(N):
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    print('Yes')


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())
lrd = []
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append((l - 1, r - 1, d))

wuf = WeightedUnionFind(n)

for item in lrd:
    if wuf.same(item[0], item[1]):
        if wuf.diff(item[0], item[1]) != item[2]:
            print('No')
            exit()
    else:
        wuf.union(item[0], item[1], item[2])

print('Yes')

Solution (Python):
visited=set()
success=1
import sys
sys.setrecursionlimit(1000000)
def dfs(graph, node):
  global visited
  global b
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b[i]=0
  dfs(a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        L, R, D = map(int, input().split())
        tree[L - 1].append((R - 1, D))
        tree[R - 1].append((L - 1, -D))

    def dfs(v):
        for u, d in tree[v]:
            if depth[u] == f_inf:
                depth[u] = depth[v] + d
                dfs(u)
            else:
                if depth[u] != depth[v] + d:
                    print("No")
                    exit()

    depth = [f_inf for _ in range(n)]
    for i in range(n):
        if depth[i] == f_inf:
            depth[i] = 0
            dfs(i)

    print("Yes")


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  





N, M = read_ints()
LRD = []
graph = defaultdict(lambda: [])
for _ in range(M):
    l, r, d = read_ints()
    l -= 1
    r -= 1
    LRD.append((l, r, d))
    graph[l].append((r, d))
    graph[r].append((l, -d))


D = [INF] * N  


def bfs(start):
    now, dist = start, 0
    que = deque([(now, dist)])
    D[now] = dist
    while que:
        now, dist = que.popleft()
        for to, co in graph[now]:
            to_dist = dist + co
            if D[to] != INF:
                if D[to] != to_dist:
                    print("No")
                    exit()
                continue
            D[to] = to_dist
            que.append((to, to_dist))


for i in range(N):
    if D[i] != INF:
        continue
    bfs(i)

print('Yes')

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

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

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

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

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

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


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    G = unionFind(N)
    for i in range(M):
        L, R, D = map(int, input().split())
        if G.same(L, R):
            x = G.getWeight(L)
            y = G.getWeight(R)
            if x == y + D:
                continue
            else:
                print("No")
                exit(0)
        else:
            G.unite(L, R, D)
    print("Yes")


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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

ans = [None] * (N + 1)

def calc(i):
    ans[i] = 0
    stack = [i]
    while stack:
        now = stack.pop()
        for next_, d in G[now]:
            if ans[next_] == None:
                ans[next_] = ans[now] + d
                stack.append(next_)
            else:
                if ans[now] + d != ans[next_]:
                    return False
    return True

for i in range(1, N + 1):
    if ans[i] == None:
        if calc(i):
            pass
        else:
            print ('No')
            exit()


max_ = -10 ** 10
min_ = +10 ** 10
for i in ans[1:]:
    max_ = max(max_, i)
    min_ = min(min_, i)

if max_ - min_ > 10 ** 9:
    print ('No')
else:
    print ('Yes')

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

class WeightedUnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self.weight = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            pa = self.root(self.parent[a])
            self.weight[a] += self.weight[self.parent[a]]
            self.parent[a] = pa
            return pa
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b,w):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self.weight[ra] = w - self.weight[a] + self.weight[b]
        else:
            self.parent[rb] = ra
            self.weight[rb] = -w - self.weight[b] + self.weight[a]
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def diff(self,a,b):
        return self.weight[a] - self.weight[b]

uf = WeightedUnionFind(N)
for l,r,d in LRD:
    l,r = l-1,r-1
    if uf.is_same(l,r):
        if uf.diff(l,r) != d:
            print('No')
            exit()
    else:
        uf.unite(l,r,d)
print('Yes')

Solution (Python):
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L,R=L-1,R-1
    G[L].append((D,R))
    G[R].append((-D,L))
ok=True
dist=[None]*N
que=deque()
for i in range(N):
    if dist[i]!=None:
        continue
    que.append(i)
    dist[i]=0
    while que:
        v=que.popleft()
        for cost,nv in G[v]:
            if dist[nv]!=None:
                if dist[nv]!=dist[v]+cost:
                    print('No')
                    exit()
            else:
                dist[nv]=dist[v]+cost
                que.append(nv)

print('Yes')

Solution (Python):
def root(x):
    if(par[x]==x):
        return x
    else:
        r=root(par[x])
        diff_weight[x]+=diff_weight[par[x]]
        par[x]=r
        return r

def weight(x):
    root(x)
    return diff_weight[x]

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

def relate(a,b,w):
    w+=weight(a);w-=weight(b)
    a=root(a)
    b=root(b)
    if(a==b):
        return False
    if rank[a]<rank[b]:
        a,b=b,a
        w=-w
    if rank[a]==rank[b]:
        rank[b]+=1
        par[b]=a
    par[b]=a
    diff_weight[b]=w
    siz[a]+=siz[b]
    return True

def size(a):
    return siz[root(a)]
    
def same(a,b):
    return root(a)==root(b)
    
N,M=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
diff_weight=[0 for _ in range(N)]

for i in range(M):
    L,R,D=map(int,input().split())
    L,R=L-1,R-1
    if same(L,R) and diff(L,R)!=D:
        print('No')
        exit()
    else:
        relate(L,R,D)
print('Yes')

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    redge=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int1,input().split())
        d+=1
        edge[l].append((r,d))
        edge[r].append((l,-d))
    s=0
    D=[-INF]*N
    used=[False]*N
    while True:
        for s in range(s,N):
            if not used[s]:
                break
        else:
            break
        D[s]=0
        stack=[s]
        while stack:
            v=stack.pop()
            used[v]=True
            for nv,d in edge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]+d
                else:
                    if D[nv]!=D[v]+d:
                        print('No')
                        exit()
                if not used[nv]:
                    stack.append(nv)
    print('Yes')


if __name__ == '__main__':
    main()

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

def main():
    N, M = map(int, input().split())
    C = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        C[l - 1].append((r - 1, d))
        C[r - 1].append((l - 1, -d))
    INF = 10 ** 10
    P = [INF] * N
    def dfs(n, p, f):
        if P[n] != INF:
            if P[n] != p:
                return False
            return True
        P[n] = p
        for i, d in C[n]:
            if i == f:
                continue
            if not dfs(i, p + d, n):
                return False
        return True
            
    for i in range(N):
        if P[i] != INF:
            continue
        if not dfs(i, 0, -1):
            return False
    return True

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

Solution (Python):
from collections import deque


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

x = [None] + [None] * n
i = 0
while i < n:
    i += 1
    if x[i] is not None:
        continue

    q = deque()
    x[i] = 0
    q.append(i)
    while q:
        x1 = q.popleft()
        for x2, d in rels[x1]:
            if x[x1] is not None and x[x2] is not None:
                if x[x2] - x[x1] != d:
                    print('No')
                    exit()
                continue
            if x[x1] is not None and x[x2] is None:
                x[x2] = x[x1] + d
                q.append(x2)
            elif x[x1] is None and x[x2] is not None:
                x[x1] = x[x2] - d
                q.append(x1)

print('Yes')

Solution (Python):
n,m=map(int,input().split())
g = [[ ] for _ in range(n)]
for _ in range(m):
    l,r,d = map(int,input().split())
    g[l-1].append((d,r-1))
    g[r-1].append((-d,l-1))
inf = 12345678901234
dist = [inf]*n

import queue
q=queue.Queue()
for i in range(n):
    if dist[i] != inf: continue
    dist[i] = 0
    q.put((0,i))
    while not q.empty():
        cost, nown = q.get()
        for nextc, nextn in g[nown]:
            if dist[nextn] != inf:
                if dist[nextn] != cost + nextc:
                    print('No')
                    exit()
            else:
                dist[nextn] = cost+nextc
                q.put((dist[nextn], nextn))
print('Yes')

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

N, M = MAP()

tree = WeightedUnionFind(N)

for _ in range(M):
	L, R, D = MAP()
	if not tree.is_same(L-1, R-1):
		tree.unite(L-1, R-1, D)
	else:
		if not tree.get_weight(L-1, R-1) == D:
			print("No")
			break
else:
	print("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()