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



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Wrong Answer

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


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

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

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

        if x == y:
            return False

        if self.parents[x] > self.parents[y]:
            x, y = y, x # xの方が木のサイズが大きいようにする
            w *= -1 # それに応じて結ぶ辺の向きも反転させる

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.diff_weight[y] = w
        return True

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

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

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

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

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from operator import itemgetter

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    """
    n個の要素を0 ~ n - 1の番号で管理する。以下の属性およびメソッドを持つ。

    parents
    各要素の親要素の番号を格納するリスト
    要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    find(x)
    要素xが属するグループの根を返す

    union(x, y)
    要素xが属するグループと要素yが属するグループとを併合する

    size(x)
    要素xが属するグループのサイズ（要素数）を返す

    same(x, y)
    要素x, yが同じグループに属するかどうかを返す

    members(x)
    要素xが属するグループに属する要素をリストで返す

    roots()
    すべての根の要素をリストで返す

    group_count()
    グループの数を返す

    all_group_members
    {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す

    __str__()
    print()での表示用
    ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """

# --------------------- #

n, m = (int(x) for x in input().split())
LRD = [tuple(int(x) for x in input().split()) for _ in range(m)]
LRD.sort(key=itemgetter(0, 1))
INF = 10**18
flags = [False] * n

uf = UnionFind(n)
for l, r, _ in LRD:
    l -= 1
    r -= 1
    uf.union(l, r)

X = [INF] * n
for root in uf.roots():
    X[root] = 0

for l, r, d in LRD:
    l -= 1
    r -= 1
    if X[l] == X[r] == INF:
        raise SystemExit
    elif X[l] != INF and X[r] == INF:
        X[r] = X[l] + d
    elif X[l] == INF and X[r] != INF:
        X[l] = X[r] - d
    else:
        if X[r] - X[l] != d:
            print("No")
            exit()
        else:
            continue

X.sort()
xmax = X[bisect_left(X, INF) - 1]
xmin = X[0]
if xmax - xmin >= 10**9:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

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

# check
base = [0] * N
for L, R, D in LRD:
    base[R - 1] = base[L - 1] + D

Contradiction = False
for L, R, D in LRD:
    if base[R - 1] - D != base[L - 1]:
        Contradiction = True
        break

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

Submission status: Wrong Answer

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

# check
base = [0] * N
for L, R, D in LRD:
    base[R - 1] += base[L - 1] + D

Contradiction = False
for L, R, D in LRD:
    if base[R - 1] - D != base[L - 1]:
        Contradiction = True
        break

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
from collections import deque
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))
q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
    x = q.popleft()
    if pos[x] ==None: pos[x] = 0
    for r,d in g[x]:
        if pos[r]==None:
            pos[r] = pos[x]+d
            q.appendleft(r)
            continue
        if pos[r] != pos[x] + d:
            print('No')
            exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

import collections
S = collections.defaultdict(list)
T = []
for _ in range(M):
    l,r,d = map(int,input().split())
    T.append([l,r,d])
    S[l].append((r,d))
T.sort()
deque = collections.deque()
dic = {}
for i in range(M):
    l,r,d = T[i]
    if l not in dic:
        dic[l] = 0
        deque.append([l,S[l]])
        while deque:
            l,s = deque.popleft()
            for r,d in s:
                if r not in dic:
                    dic[r] = d
                    deque.append([r,S[r]])
                else:
                    if dic[l] != dic[r]-d: print('No');exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = []
for _ in range(M):
    l,r,d = map(int,input().split())
    S.append([l,r,d])
S.sort()
dic = {}
for i in range(M):
    l,r,d = S[i]
    if l not in dic:
        if r not in dic:
            dic[l] = 0
            dic[r] = d
        else:
            dic[l] = dic[r]-d
    else:
        if r not in dic:
            dic[r] = dic[l]+d
        elif dic[r] != d + dic[l]:
            print('No');exit()
print('Yes')

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

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

pos = deque([i for i in range(N)])
point = [-1] * N

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

print("Yes")

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

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

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

print("Yes")

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

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

point = [-1] * N
pos = deque([i for i in range(N)])

while len(pos) > 0:
    now = pos.popleft()
    # 最初の一つ
    if point[now] == -1:
        point[now] = 0
    for next, dis in dist[now]:
        if point[next] == -1:
            point[next] = point[now] + dis
            pos.append(next)
            continue
        if point[next] - point[now] != dis:
            print('No')
            exit()

print("Yes")

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

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

point = [-1] * N

pos = deque([i for i in range(N)])
while len(pos) > 0:
    now = pos.popleft()
    # 最初の一つ
    if point[now] == -1:
        point[now] = 0
    for next, dis in dist[now]:
        if point[next] == -1:
            point[next] = point[now] + dis
            pos.appendleft(next)
            continue
        if point[next] - point[now] != dis:
            print('No')
            exit()

print('Yes')

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

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

point = [-1] * N

pos = deque([i for i in range(N)])
while len(pos) > 0:
    now = pos.popleft()
    # 最初の一つ
    if point[now] == -1:
        point[now] = 0
    for next, dis in dist[now]:
        if point[next] == -1:
            point[next] = point[now] + dis
            pos.append(next)
            continue
        if point[next] - point[now] != dis:
            print('No')
            exit()

print('Yes')

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = getNM()
query = [getList() for i in range(M)]
# グラフは森の可能性がある
U = UnionFind(N)

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

def judger(sta):
    point = [-1] * N
    point[sta] = 0

    pos = deque([[sta, 0]])
    while len(pos) > 0:
        u, dis = pos.popleft()
        for i in dist[u]:
            if point[i[0]] == -1:
                point[i[0]] = point[u] + i[1]
                pos.append([i[0], i[1]])
            else:
                if point[i[0]] - point[u] != i[1]:
                    print('No')
                    exit()

for num in U.all_group_members().values():
    st = -1
    for i in num:
        if len(dist[i]) > 0:
            st = i
            break
    if st >= 0:
        judger(st)
print('Yes')

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = getNM()
query = [getList() for i in range(M)]
# グラフは森の可能性がある
U = UnionFind(N)

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

def judger(sta):
    point = [-1] * N
    point[sta] = 0

    pos = deque([[sta, 0]])
    while len(pos) > 0:
        u, dis = pos.popleft()
        for i in dist[u]:
            if point[i[0]] == -1:
                point[i[0]] = point[u] + i[1]
                pos.append([i[0], i[1]])
            else:
                if point[i[0]] - point[u] != i[1]:
                    print('No')
                    exit()

for num in U.all_group_members().values():
    st = 0
    for i in num:
        if len(dist[i]) > 0:
            st = i
            break
    judger(st)

print('Yes')

Submission status: Wrong Answer

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

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

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

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


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(M)]

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

sta = 0
for i in range(N):
    if len(dist[i]) > 0:
        sta = i
        break

point = [-1] * N
point[sta] = 0

pos = deque([[sta, 0]])

while len(pos) > 0:
    u, dis = pos.popleft()
    for i in dist[u]:
        if point[i[0]] == -1:
            point[i[0]] = point[u] + i[1]
            pos.append([i[0], i[1]])
        else:
            if point[i[0]] - point[u] != i[1]:
                print('No')
                exit()
print('Yes')

Submission status: Wrong Answer

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

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

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

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

"""
# BFS解放
flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf: # 偽の場合、連結で既に訪れている
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')
"""

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

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

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

class WeightedUnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0] * n
        # 根への距離を管理
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

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

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

if __name__ == '__main__':
    main()