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:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.weight[x] = w
            self.par[x] = y
        else:
            self.weight[y] = -w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.weight[y] = w
            self.par[x] = y
        else:
            self.weight[y] = -w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)
    

wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w += self.weighting(x)
        w -= self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.weight[y] = w
            self.par[y] = x
        else:
            self.weight[x] = -w
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return -(self.weighting(x) - self.weighting(y))


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")
for i in range(N+1):
    wuf.find(i)

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.weight[x] = -w
            self.par[x] = y
        else:
            self.weight[y] = -w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]
 
 
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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]
 
    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.weight[x] = w
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)
 
 
wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

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

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        print(wuf.diff(l,r))
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]
 
 
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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]
 
    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]
 
    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)
 
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    # 各頂点間の絶対距離
    def diff(self, x, y):
        return abs(self.weighting(x) - self.weighting(y))
 
 
wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return abs(self.weighting(x) - self.weighting(y))


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        print(wuf.diff(l, r))
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            w = -w
            self.weight[y] = w
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    # 同じ集合に属するか検索
    def same(self, x, y):
        return self.find(x) == self.find(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.weighting(l) - wuf.weighting(r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

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


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

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

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        wx = self.weighting(x)
        wy = self.weighting(y)
        x = self.find(x)
        y = self.find(y)
        if wx > wy + w:
            self.par[y] = x
            self.weight[y] += wx - w
        else:
            self.par[x] = y
            self.weight[x] += w

    # 同じ集合に属するか検索
    def same(self, x, y):
        return self.find(x) == self.find(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.weighting(l) - wuf.weighting(r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)


else:
    print("Yes")

Submission status: Wrong Answer

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


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

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

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y
        self.weight[x] += w

    # 同じ集合に属するか検索
    def same(self, x, y):
        return self.find(x) == self.find(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.weighting(l) - wuf.weighting(r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
gr = {i: [] for i in range(1, n + 1)}
ans = "Yes"

for _ in range(m):
    l, r, d = map(int, input().split())
    if l < r:
        gr[l].append((r, d))
    else:
        gr[r].append((l, -d))
pos = [-1 for _ in range(n + 1)]
for u in range(1, n + 1):
    if pos[u] < 0:
        pos[u] = int(1e9)
    for (v, d) in gr[u]:
        if pos[v] < 0:
            pos[v] = pos[u] + d
        elif pos[v] != pos[u] + d:
            ans = "No"
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

x = [None for _ in range(n)]

def check(y):
    for z,d in a[y]:
        if x[z] is None:
            x[z] = x[y] + d
            return check(z)
        elif x[z] != x[y] + d:
            return False
    return True

for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not check(i):
            print('No')
            exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [set() for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].add((r-1,d))
            e[r-1].add((l-1,-d))

    b = [None] * n

    for i in range(n):
        if b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'
                    if e[r] in (j,-d):
                        e[r].remove((j,-2))

    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, size):
        self.table = [[-1, 0] for _ in range(size + 1)]

    def find(self, x):
        n, d = self.table[x] 
        if n < 0:
            return [x, d]
        else:
            n1, d1 = self.find(n)
            r = [n1, d1 + d]
            self.table[x] = r
            return r

    # 併合
    def union(self, x, y, d):
        n1, d1 = self.find(x)
        n2, d2 = self.find(y)
        if n1 != n2:
            if self.table[n1][0] <= self.table[n2][0]:
                # 小さいほうが個数が多い
                self.table[n1][0] -= 1
                self.table[n2] = [n1, d1+d]
            else:
                self.table[n2][0] -= 1
                self.table[n1] = [n2, d2-d]
        else:
            print(d1, d2, d)
            if d2 - d1 != d:
                return False
        return True

def solve(N, M, lrd):
    uf = UnionFind(N)
    for l, r, d in lrd:
        if not uf.union(l, r, d):
            return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(200002)

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

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


ds = [None for _ in range(n + 1)]


def check(v):
    for next_v, d in g[v]:
        if ds[next_v] is None:
            ds[next_v] = ds[v] + d
            if check(next_v) is False:
                return False
        elif not (ds[next_v] - ds[v] == d):
            return False
    return True


valid = True
for v in range(n):
    if ds[v] is None:
        ds[v] = 0
    if check(v):
        valid = False
        break

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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


checked = {}
ds = defaultdict(int)


def check(v, cur_d=0):
    if (not (v in ds)):
        ds[v] = cur_d
    if v in checked:
        return True
    checked[v] = True
    for next_v, d in g[v]:
        if not (next_v in ds):
            ds[next_v] = ds[v] + d
        elif not (ds[next_v] - ds[v] == d):
            return False
        elif check(next_v) is False:
            return False
    return True


valid = True
for v in range(1, n + 1):
    if v in checked:
        continue
    valid &= check(v)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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


checked = {}
ds = defaultdict(int)


def check(v, prev=-1, cur_d=0):
    if prev == -1 and (not (v in ds)):
        ds[v] = cur_d
    if v in checked:
        return True
    checked[v] = True
    for next_v, d in g[v]:
        if not (next_v in ds):
            ds[next_v] = ds[v] + d
        elif not (ds[next_v] - ds[v] == d):
            return False
        elif check(next_v, prev=v) is False:
            return False
    return True


valid = True
for v in range(1, n + 1):
    if v in checked:
        continue
    valid &= check(v)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

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


checked = {}
ds = defaultdict(int)


def check(v, prev=-1, cur_d=0):
    if prev == -1 and (not (v in ds)):
        ds[v] = cur_d
    if v in checked:
        return True
    checked[v] = True
    for next_v, d in g[v]:
        if not (next_v in ds):
            ds[next_v] = ds[v] + d
            ds[v] = ds[next_v] - d
        elif not (ds[next_v] - ds[v] == d):
            return False
        elif check(next_v, prev=v) is False:
            return False
    return True


valid = True
for v in range(1, n + 1):
    if v in checked:
        continue
    valid &= check(v)

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

Submission status: Wrong Answer

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

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

	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')

	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L, R)

	memo[s] = 0


	for i in range(len(dist)):
		for v, d in dist[i]:
			if i in memo:
				if v in memo:
					f = memo[v] == memo[i] + d
					if not f:
						print("No")
						exit()
				else:
					if i in memo:
						memo[v] = memo[i] + d
			else:
				memo[i] = d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys,collections;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,m = Is()

class Cand:
    os = 0
    d = {}
    def setOS(self, os):
        self.os += os
    def append(self,lis):
        self.d.update(lis)
    def get(self,key):
        return self.d[key]+self.os
        
cands = []
for i in range(m):
    L,R,D = Is()
    flag = True
    c = 0
#    print(L,R,D)
    for i,e in enumerate(cands):
        if L in e.d and R in e.d:
#            print(D,e.get(R)-e.get(L))
            if D != e.get(R)-e.get(L):
                print("No")
                exit()
            flag = False
            break
        elif L in e.d and not R in e.d:
            if not flag:
                cands[c].setOS(D)
            e.append({R:e.d[L]+D})
#            print(e.d)
            flag = False
            c = i
        elif R in e.d and not L in e.d:
            if not flag:
                cands[i].setOS(D)
            e.append({L:e.d[R]-D})
#            print(e.d)
            flag = False
            c = i
    if flag:
        cand = Cand()
        cand.append({L:0})
        cand.append({R:D})
        cands.append(cand)
#        print(cands[-1].d)
print("Yes")

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [[-1, 0] for _ in range(size + 1)]

    def find(self, x):
        n, d = self.table[x] 
        if n < 0:
            return [x, d]
        else:
            n1, d1 = self.find(n)
            r = [n1, d1 + d]
            self.table[x] = r
            return r

    # 併合
    def union(self, x, y, d):
        n1, d1 = self.find(x)
        n2, d2 = self.find(y)
        if n1 != n2:
            if self.table[n1][0] <= self.table[n2][0]:
                # 小さいほうが個数が多い
                self.table[n2] = [n1, d1+d]
            else:
                self.table[n2][0] -= 1
                self.table[n1] = [n2, d2-d]
        else:
            print(d1, d2, d)
            if d2 - d1 != d:
                return False
        return True

def solve(N, M, lrd):
    uf = UnionFind(N)
    for l, r, d in lrd:
        if not uf.union(l, r, d):
            return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")