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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False
                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False

                con[2] = True
                if not visited[t]:
                    print('hogehoge')
                    #dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False

                con[2] = True
                #if not visited[t]:
                #    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            return True
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False

                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False
                return True

                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, M =map(int, input().split())
G=[[]for i in range(N+1)]
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,-c),

d = [10**9]*(N+1)
flag = True
def f(v, u):
    global flag
    if not flag:
        d[v] = 0
        return 0
    else:
        d[v] = u
        for t, c in G[v]:
            if d[t] == 10**9:
                f(t, u+c)
            else:
                if d[t] != u+c:
                    flag = False
                else:
                    return 0
for i in range(1, N+1):
    if d[i] == 10**9:
        f(i, 0)
if flag:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

INF = float("inf")
x = [INF] * n
info = [[]] * m
for i in range(m):
  l, r, d = map(int, input().split())
  # l < rならそのまま入れる、l > r なら [r, l, -d]で入れることで、要素の一つ目が常に二つ目より小さくなるようにする
  # こうしておかないとのちに条件分岐が割と出てきてめんどくさい
  if l < r:
    info[i] = [l, r, d]
  else:
    info[i] = [r, l, -d]
  
info.sort()  
#print(info)
for i in range(m):
  #print(x)
  if i  == 0:
    # xは初回のrから各人までの距離とする
    x[info[i][0]-1] = 0
    x[info[i][1]-1] = info[i][2]
    
  else:
    if x[info[i][0]-1] != INF:
      # 左は決まっている場合
      if x[info[i][1]-1] != INF:
        #左右ともに決まってるので矛盾がないか確認
        if x[info[i][0]-1] + info[i][2] != x[info[i][1]-1]:
          print("No")
          exit()
      else:
        # 左は決まっているが右は決まってないので、左＋ｄを右に代入
        x[info[i][1]-1] = x[info[i][0]-1] + info[i][2]
    else:
      # 左が決まってない場合
      if x[info[i][1]-1] != INF:
        # 右は決まっている場合、左＝右 - dを代入
        x[info[i][0]-1] = x[info[i][1]-1] - info[i][2]     
      else:
        # 右も決まってない場合はあとからどうとでも取れるからスキップ???
        continue

            
            
print("Yes")

Submission status: Wrong Answer

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

# uf treeの亜種


N,M = map(int,input().split())
root = list(range(N+1))
pos = [0] * (N+1) # rootからの相対座標
depth = [0] * (N+1)

def find_root(x):
  # root および 相対座標 を返す
  y = root[x]
  if x == y:
    return y,0
  z,p = find_root(y)
  root[x] = z
  pos[x] += p
  return z,pos[x]

def merge(x,y,d):
  # y = x + dという位置関係
  rx,px = find_root(x)
  ry,py = find_root(y)
  if rx == ry:
    return (py == px + d)
  if depth[rx] > depth[ry]:
    root[ry] = rx
    pos[ry] = d
  else:
    root[rx] = ry
    pos[rx] = -d
    depth[ry] += 1
  return True

answer = 'Yes'
for _ in range(M):
  L,R,D = map(int,input().split())
  if not merge(L,R,D):
    answer = 'No'
    break
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
weight = [0] * (n + 1)

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        weight[x] += weight[parent[x]]
        return parent[x]

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

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

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

ans = "Yes"
for i in range(m):
    l, r, d = map(int, input().split())
    if same_check(l, r):
        if diff(l, r) != d or diff(l, r) < 0 or diff(l, r) > 10 ** 9:
            ans = "No"
            break
    else:
        union(l, r, d)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
weight = [0] * (n + 1)

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        weight[x] += weight[parent[x]]
        return parent[x]

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

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

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

ans = "Yes"
for i in range(m):
    l, r, d = map(int, input().split())
    if same_check(l, r):
        if diff(l, r) != d:
            ans = "No"
            break
    else:
        union(l, r, d)
print(ans)

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        wei[x] += wei[par[x]]
        return par[x]

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

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

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*n
wei = [0]*n

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

Submission status: Wrong Answer

Solution code:
#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        wei[x] += wei[par[x]]
        return par[x]

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return wei[y]-wei[x]

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

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*n
wei = [0]*n

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,sys.stdin.readline().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=[False]*200001
for i in xrange(M):
    l,r,d=map(int,sys.stdin.readline().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200001
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done[c]=True
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r] is None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    elif X[r]!=None:
        if X[l] is None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    else:
        sys.exit(1)
    if ll:            
        for c in C[l]:
            if not done[c]:
                Q.put(c); done[c]=True
    if rr:
        for c in C[r]:
            if not done[c]:
                Q.put(c); done[c]=True
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,sys.stdin.readline().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=[False]*200001
for i in xrange(M):
    l,r,d=map(int,sys.stdin.readline().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200001
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done[c]=True
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
                Q.put(c); done[c]=True
    if rr:
        for c in C[r]:
                Q.put(c); done[c]=True
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,sys.stdin.readline().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=[False]*200001
for i in xrange(M):
    l,r,d=map(int,sys.stdin.readline().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200001
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done[c]=True
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
            if not done[c]:
                Q.put(c); done[c]=True
    if rr:
        for c in C[r]:
            if not done[c]:
                Q.put(c); done[c]=True
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,sys.stdin.readline().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=[False]*200000
for i in xrange(M):
    l,r,d=map(int,sys.stdin.readline().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done[c]=True
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
            if not done[c]:
                Q.put(c); done[c]=True
    if rr:
        for c in C[r]:
            if not done[c]:
                Q.put(c); done[c]=True
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,raw_input().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=[False]*200000
for i in xrange(M):
    l,r,d=map(int,raw_input().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done[c]=True
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
            if not done[c]:
                Q.put(c); done[c]=True
    if rr:
        for c in C[r]:
            if not done[c]:
                Q.put(c); done[c]=True
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,raw_input().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=set()
for i in xrange(M):
    l,r,d=map(int,raw_input().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done.add(c)
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
            if c not in done:
                Q.put(c); done.add(c)
    if rr:
        for c in C[r]:
            if c not in done:
                Q.put(c); done.add(c)            
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,raw_input().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=set()
for i in xrange(M):
    l,r,d=map(int,raw_input().split())
    if l<=r:
        L.append(l);R.append(r);D.append(d)
    else:        
        L.append(r);R.append(l);D.append(-d)
    C[l].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done.add(c)
while not Q.empty():
    q=Q.get()
    #print(q)
    l=L[q];r=R[q];d=D[q]
    ll=rr=False
    if X[l]!=None:
        if X[r]==None:
            rr=True
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            ll=True
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    if ll:            
        for c in C[l]:
            if c not in done:
                Q.put(c); done.add(c)
    if rr:
        for c in C[r]:
            if c not in done:
                Q.put(c); done.add(c)            
    #print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,raw_input().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=set()
for i in xrange(M):
    l,r,d=map(int,raw_input().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done.add(c)
while not Q.empty():
    q=Q.get()
    print(q)
    l=L[q];r=R[q];d=D[q]
    if X[l]!=None:
        if X[r]==None:
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    for c in C[l]:
        if c not in done:
            Q.put(c); done.add(c)
    for c in C[r]:
        if c not in done:
            Q.put(c); done.add(c)            
    print(X[:11])
print("Yes")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,raw_input().split())
L=[];R=[];D=[]
C=defaultdict(list)
done=set()
for i in xrange(M):
    l,r,d=map(int,raw_input().split())
    L.append(l);R.append(r);D.append(d)
    C[l].append(i);C[r].append(i)
if M==0:
    print("Yes")
    sys.exit(0)
X=[None]*200000
X[l]=0
Q=Queue()
for c in C[l]:
    Q.put(c)
    done.add(c)
while not Q.empty():
    q=Q.get()
    l=L[q];r=R[q];d=D[q]
    if X[l]!=None:
        if X[r]==None:
            X[r]=X[l]+d
        else:
            if X[r]!=X[l]+d: 
                print("No")
                sys.exit(0)
    else:
        if X[l]==None:
            X[l]=X[r]-d
        else:
            if X[r]!=X[l]+d:
                print("No")
                sys.exit(0)
    for c in C[l]+C[r]:
        if c not in done:
            Q.put(c); done.add(c)

print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind(object):#インデックスに注意
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        #根からの距離
        self.diff_weight=[0 for _ in range(size)]

    def find(self, x):#根を探す
        if self.parent[x] == x:#根なら返す
            return x
        else:
            self.diff_weight[x] += self.diff_weight[self.parent[x]]
            self.parent[x] = self.find(self.parent[x])#一度調べた値を根につなぎ直す
            return self.parent[x]
    def weight(self, x):
        self.find(x);
        return self.diff_weight[x]
    

    def unite(self, x, y, w):#要素、要素、その間のweight
        #根を探す
        rx = self.find(x)
        ry = self.find(y)
        if x == y:#すでに同じグループにいれば何もしない
            return

        if self.rank[rx] < self.rank[ry]:#yの方が高い場合
            self.parent[rx] = ry#yの根にxの根をつなぐ
            
            #xの根のweightをxとyの間のweightがwになるように更新
            self.diff_weight[rx]=w - self.diff_weight[x] + self.diff_weight[y]
        else:
            self.parent[ry] = rx
            self.diff_weight[ry] = -w - self.diff_weight[y] + self.diff_weight[x]
            if self.rank[rx] == self.rank[ry]:#同じ高さの時
                self.rank[x] += 1#片方の高さを＋１する
        #終わった時点では根ではない点のweightは更新されていないことに注意

    def same(self, x, y):#同じ集合に属するか？
        return self.find(x) == self.find(y)
    # xからyへのコスト
    def diff(self, x, y):
        if self.same(x, y):
            return self.weight(x) - self.weight(y)
n, m=map(int, input().split())
U=WeightedUnionFind(n)
def C(U):
    for i in range(m):
        l, r, d = map(int, input().split())
        if U.same(l-1, r-1):
            if U.diff(l-1, r-1)!=d:
                return False
        else:
            U.unite(l-1, r-1, d)
    return True
if C(U):
    print('Yes')
else:
    print('No')