Problem:
 Score : 400 points    Problem Statement There are N people standing on the x -axis.
Let the coordinate of Person i be x_i .
For every i , x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.  You will given M pieces of information regarding the positions of these people.
The i -th piece of information has the form (L_i, R_i, D_i) .
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.  It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.      Constraints  1 \leq N \leq 100  000  0 \leq M \leq 200  000  1 \leq L_i, R_i \leq N ( 1 \leq i \leq M )  0 \leq D_i \leq 10  000 ( 1 \leq i \leq M )  L_i \neq R_i ( 1 \leq i \leq M )  If i \neq j , then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j) .  D_i are integers.         Input Input is given from Standard Input in the following format:  N  M  L_1  R_1  D_1  L_2  R_2  D_2  :  L_M  R_M  D_M       Output If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes ; if it does not exist, print No .        Sample Input 1 3 3
1 2 1
2 3 1
1 3 2      Sample Output 1 Yes  Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103) .       Sample Input 2 3 3
1 2 1
2 3 1
1 3 5      Sample Output 2 No  If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.       Sample Input 3 4 3
2 1 1
2 3 5
3 4 2      Sample Output 3 Yes       Sample Input 4 10 3
8 7 100
7 9 100
9 8 100      Sample Output 4 No       Sample Input 5 100 0      Sample Output 5 Yes

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    s, t, d = map(int, input().split())
    edge[s].append((t, d))
    edge[t].append((s, -d))

dist = [None] * (N + 1)


def isOK(v):
    node = [v]
    if dist[v] is None:
        dist[v] = 0

    while node:
        s = node.pop()
        for t, d in edge[s]:
            if dist[t] is None:
                dist[t] = dist[s] + d
                node.append(t)
            else:
                if dist[t] != dist[s] + d:
                    return False
    return True


ans = "Yes"
for i in range(1, N + 1):
    if dist[i] is not None:
        continue

    if not isOK(i):
        ans = "No"
        break
print(ans)

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 i in Q:
				for j,d in edge[i]:
					if ans[j]==10**10:
						P+=[j]
						ans[j]=ans[i]+d
			Q=P
for i in range(n):
	for j,k in edge[i]:
		if ans[i]+k!=ans[j]:print("No");exit()
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 i in Q:
				for j,d in edge[i]:
					if ans[j]==10**10:
						P+=[j]
						ans[j]=ans[i]+d
			Q=P
for i in range(n):
	for j,k in edge[i]:
		if ans[i]+k!=ans[j]:print("No");exit()
print("Yes")

Solution (Python):
import sys

input = sys.stdin.buffer.readline

n, m =map(int, input().split())
g = [[] for _ 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))

s = []
visit = [-1]*n
dist = [False]*n
for i in range(n):
    if visit[i] == -1:
        s.append(i)
        visit[i] = 0
        dist[i] = 0
        while s:
            v = s.pop()
            for d, u in g[v]:
                if dist[u]:
                    if dist[u] != dist[v]+d:
                        print('No')
                        exit()
                if visit[u] == -1:
                    visit[u] = 0
                    dist[u] = dist[v]+d
                    s.append(u)
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):
n, m = map(int, input().split())
inf = 10**10

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

D = [inf for i in range(n)]

for i in range(n):
    if D[i] != inf:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        for k in G[j].keys():
            if D[k] == inf:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

Solution (Python):
n, m = map(int, input().split())
inf = 10**10
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l-1][r-1] = d
    G[r-1][l-1] = -d
V = [False for i in range(n)]
D = [inf for i in range(n)]
for i in range(n):
    if V[i]:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        V[j] = True
        for k in G[j].keys():
            if not V[k]:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

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

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

visited = [0]*N
dist = [0]*N

for i in range(N):
    if visited[i]:  
        continue
    visited[i] = 1  
    stack = [i]  
    vset = set()  

    while stack:
        v = stack.pop()  
        vset.add(v)  
        for dest, d in adj[v]:
            if visited[dest]:
                continue
            visited[dest] = 1  
            dist[dest] = dist[v] + d  
            stack.append(dest)

    for v in vset:  
        for dest, d in adj[v]:
            if dist[v] + d != dist[dest]:  
                print('No')  
                exit()

print('Yes')

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

for l, r, d in (map(int, l.split()) for l in sys.stdin):
    adj[l-1].append((r-1, d))
    adj[r-1].append((l-1, -d))

visited = [0]*N
dist = [0]*N

for i in range(N):
    if visited[i]:  
        continue
    visited[i] = 1  
    stack = [i]  
    vset = set()  

    while stack:
        v = stack.pop()  
        vset.add(v)  
        for dest, d in adj[v]:
            if visited[dest]:
                continue
            visited[dest] = 1  
            dist[dest] = dist[v] + d  
            stack.append(dest)

    for v in vset:  
        for dest, d in adj[v]:
            if dist[v] + d != dist[dest]:  
                print('No')  
                exit()

print('Yes')

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

INF = float('inf')
dist = [INF]*N
seen = [False]*N
q = deque([])
for s in range(N):
    if dist[s] != INF:
        continue
    q.append([s,0])
    while len(q) != 0:
        p = q.popleft()
        
        
        
        if seen[p[0]] and dist[p[0]] != p[1]: 

            
            print('No')
            exit()
        
        if seen[p[0]] and dist[p[0]] == p[1]: 
            continue
        dist[p[0]] = p[1]
        seen[p[0]] = True
        for np in D[p[0]]:
            q.append([np[0],p[1]+np[1]])
print('Yes')

Solution (Python):
def main():
  
  def find(x):
      if par[x] < 0:
          return x
      else:
          px = find(par[x])
          wei[x] += wei[par[x]]
          par[x] = px
          return px

  
  def weight(x):
      find(x)
      return wei[x]


  
  def unite(x,y,w):
      w += wei[x]-wei[y]
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          
          if par[x] > par[y]:
              x,y = y,x
              w = -w
          par[x] += par[y]
          par[y] = x
          wei[y] = w
          return True

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

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

  import sys
  input = sys.stdin.readline  
  n,m = [int(i) for i in input().split()]
  par = [-1]*n
  wei = [0]*n

  for i in range(m):
    l,r,d = [int(i) for i in input().split()]
    if not same(l-1,r-1):
      unite(l-1,r-1,d)
    else:
      if diff(l-1,r-1) == d:
        continue
      else:
        print('No')
        exit()

  print('Yes')
if __name__ == '__main__':
    main()

Solution (Python):



def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return wei[x]



def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True


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


def diff(x,y):
    return weight(y)-weight(x)
  
import sys
input = sys.stdin.readline  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

for i in range(m):
  l,r,d = [int(i) for i in input().split()]
  if not same(l-1,r-1):
    unite(l-1,r-1,d)
  else:
    if diff(l-1,r-1) == d:
      continue
    else:
      print('No')
      exit()

print('Yes')

Solution (Python):



def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return wei[x]



def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True


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


def diff(x,y):
    return weight(y)-weight(x)
  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

for i in range(m):
  l,r,d = [int(i) for i in input().split()]
  if not same(l-1,r-1):
    unite(l-1,r-1,d)
  else:
    if diff(l-1,r-1) == d:
      continue
    else:
      print('No')
      exit()

print('Yes')

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [None] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] is None:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [None] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] is None:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [None] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 0
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == None:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Solution (Python):
n, m = map(int, input().split())
ed = [[] for _ in range(n)]  
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  
  ed[r-1].append((l-1, -d))  

visited = [False] * n  

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(p):
  for edge in g[p]:
    if x[edge[0]] is not None:
      if x[edge[0]]-x[p]!=edge[1]:
        print('No')
        exit()
    else:
      x[edge[0]]=x[p]+edge[1]
      dfs(edge[0])
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  l,r,d=map(int,input().split())
  g[r-1].append((l-1,d))
  g[l-1].append((r-1,-d))
x=[None]*n
for i in range(n):
  if x[i]==None:
    x[i]=0
    dfs(i)
print('Yes')

Solution (Python):
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  for _ in range(m):
    a, b, c = map(int, input().split())
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

print(main())

Solution (Python):
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  for _ in range(m):
    a, b, c = map(int, input().split())
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

if __name__ == '__main__':
  print(main())

Solution (Python):
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  q = [tuple(map(int, input().split())) for _ in range(m)]
  for a, b, c in q:
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

if __name__ == '__main__':
  print(main())

Solution (Python):
from collections import deque

N, M = map(int, input().split())
graph = [[] for _ 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])
X = [None] * N


def bfs(u):
    que = deque([(u, 0)])
    X[u] = 0
    while que:
        u, x = que.popleft()
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for i in range(N):
    if X[i] is None:
        bfs(i)
print('Yes')

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index):
        if self.parent[index] == index:  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2):  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

    def getComponent(self):
        return self.component

N, M = map(int, input().split())
INF = 10**18
tree = UnionFind(N)

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

minDist = [INF] * N
for start in range(N):
    if tree.root(start) != start:
        continue
    st = [(start, 0)]
    while st:
        now, dist = st.pop()

        if minDist[now] == dist:
            continue

        if minDist[now] != INF and minDist[now] != dist:
            print('No')
            exit()
        minDist[now] = dist

        for to, d in edges[now]:
            if minDist[to] == d + dist:
                continue
            st.append((to, dist + d))

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((R-1, D))
    G[R-1].append((L-1, -D))

dist = [0] * N
visited = [False] * N

def dfs(v:int):
    """ 矛盾がある -> True """
    stack = [v]
    dist[v] = 0
    visited[v] = True

    while stack:
        v = stack.pop()
        d = dist[v]
        for to, cost in G[v]:
            if visited[to]:
                if dist[to] != d + cost:
                    return True
            else:
                visited[to] = True
                dist[to] = d + cost
                stack.append(to)
    
    return False

flag = True
for v in range(N):
    if not visited[v]:
        if dfs(v):
            flag = False
            break

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())

    par = [i for i in range(N)]
    rank = [1]*N
    weight = [0]*N

    def find_root(x):
        if par[x] == x:
            return x
        else:
            r = find_root(par[x])
            weight[x] += weight[par[x]]
            par[x] = r
            return par[x]

    def get_weight(x):
        find_root(x)
        return weight[x]

    def get_diff(x, y):
        return get_weight(y) - get_weight(x)

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y, w):
        w += get_weight(x)
        w -= get_weight(y)
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
            w = -w
        rank[x] += rank[y]
        par[y] = x
        weight[y] = w

    def size(x):
        
        return rank[find_root(x)]

    for i in range(M):
        le, ri, d = (int(i) for i in input().split())
        le -= 1
        ri -= 1
        if is_same_group(le, ri):
            diff = get_diff(le, ri)
            if diff != d:
                return print("No")
        else:
            unite(le, ri, d)
    print("Yes")


if __name__ == '__main__':
    main()

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

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

g = [[] for _ in range(n)]
edge = [{} for _ in range(n)]

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

s = []
visit = [10**18]*n
for i in range(n):
    if visit[i] != 10**18:
        continue
    s.append(i)
    visit[i] = 0
    while s:
        v = s.pop()
        for u in g[v]:
            if visit[u] != 10**18:
                if visit[u] != visit[v]+edge[v][u]:
                    print('No')
                    exit()
            else:
                visit[u] = visit[v]+edge[v][u]
                s.append(u)
else:
    print('Yes')

Solution (Python):
from collections import deque

n, m = map(int, input().split())
info = [[] for _ in range(n)]
visited = [0] * n
dist = [0] * n
ans = 'Yes'
for i in range(m):
    l, r, D = map(int, input().split())
    info[l-1].append([r-1, D])
    info[r-1].append([l-1, -D])

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append(i)
    while q:
        p = q.pop()
        for x, d in info[p]:
            if visited[x] == 0:
                visited[x] = 1
                dist[x] = dist[p] + d
                q.append(x)
            elif dist[x] != dist[p] + d:
                ans = 'No'

print(ans)

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        Edge[l-1].append((r-1, d))
        Edge[r-1].append((l-1, -1 * d))
    Dist = [10 ** 20] * N
    possible = True
    for i in range(N):
        if Dist[i] == 10 ** 20:
            q = deque()
            q.append((i, 0))
            while q:
                nn, nd = q.popleft()
                if Dist[nn] == 10 ** 20:
                    Dist[nn] = nd
                    for ne, add in Edge[nn]: q.append((ne, nd + add))
                else:
                    if Dist[nn] == nd: continue
                    else:
                        possible = False
                        break
            if not possible:
                print("No")
                break
    else: print("Yes")

    return 0

if __name__ == "__main__":
    solve()

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

    S=[(i,0) for i in range(N) if ny[i]==0]
    D=[-1]*N
    while S:
        v,dv = S.pop()
        if D[v] >= 0:
            if D[v] != dv:
                print('No')
                exit()
            continue
        D[v] = dv
        for to,d in G[v]:
            S.append((to,dv+d))
    if D.count(-1) > 0:
        print('No')
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Solution (Python):


import sys

sys.setrecursionlimit(10**9)

def dfs(l,d):
    loc[l]=d
    for n_l,n_d in way[l]:
        if loc[n_l]==10**9:
            dfs(n_l,d+n_d)
        elif loc[n_l]!=d+n_d:
            print("No")
            exit()

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

way=[[] for i in range(N)]
loc=[10**9]*N

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

for i in range(N):
    if loc[i]==10**9:
        dfs(i,0)

print("Yes")

Solution (Python):









import sys
read = sys.stdin.readline


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


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


from collections import defaultdict, deque

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


X = [None] * N  


def bfs(u):  
    que = deque([(u, 0)])  
    X[u] = 0
    while que:
        u, x = que.popleft()
        
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for u in range(N):
    if X[u] is None:
        bfs(u)
print('Yes')

Solution (Python):






import sys
read = sys.stdin.readline


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


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


from collections import defaultdict, deque

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


X = [None] * N  


def bfs(u):  
    que = deque([(u, 0)])  
    X[u] = 0
    while que:
        u, x = que.popleft()
        
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for u in range(N):
    if X[u] is None:
        bfs(u)
print('Yes')

Solution (Python):

import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def GetWeight(self, x):
        self.Find_Root(x)
        return self.weight[x]
    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False
        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        self.root[y] = x
        self.weight[y] = w
        return True
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for l, r, d in lrd:
    if uf.isSameGroup(l, r)==False:
        uf.Unite(l, r, d)
    else:
        if uf.Diff(l, r) != d:
            print('No')
            exit()
print('Yes')