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: Runtime Error

Solution code:
x = {}
n, m = map(int, raw_input().split())
if m == 0:
    print 'Yes'
    exit()
l, r, d = map(int, raw_input().split())
x[l], x[r] = 0, d
flag = True
for _ in xrange(m - 1):
    l, r, d = map(int, raw_input().split())
    if r in x:
        if x[r] != x[l] + d:
            flag = False
    else:
        x[r] = x[l] + d
print 'Yes' if flag else 'No'

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

DP = [None] * 100000

for i, j, k in sorted(list(zip(L, R, D))):
    if DP[i] != None and DP[j] != None:
        if DP[j] != DP[i] + k:
            print('No')
            sys.exit()
    if DP[i] == None and DP[j] == None:
        DP[i] = 0
        DP[j] = DP[i] + k
    if DP[i] == None and DP[j] != None:
        DP[i] = DP[j] - k
    if DP[i] != None and DP[j] == None:
        DP[j] = DP[i] + k

print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = [int(a) for a in input().split()]
LRD_ = []
for i in range(M):
    LRD_.append([int(a) for a in input().split()])

LRD = sorted(LRD_, key=lambda x: min(x[0], x[1]))
place = np.ones(N+1) * -1

if M == 0 or N == 1:
    print("Yes")
    exit(0)
    
l,r,d = LRD.pop(0)
place[l] = 0
place[r] = place[l] + d
for l, r, d in LRD:
    if place[l] == -1 and place[r] == -1:
        assert False
    if place[r] == -1:
        place[r] = place[l] + d
        continue
    if place[l] == -1:
        place[l] = place[r] - d
        continue
    if place[r] != place[l] + d:
        print("No")
        exit(0)
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
import heapq
def dijkstra(N,start, goal,E):
    """最短距離,経路を返すプログラム"""
    dist = [float('inf')] * N          #dist[i]:始点からの距離
    path = [tuple() for n in range(N)] #path[i]:(start,...,i)までの経路をカンマで区切ったもの
    dist[start] = 0
    path[start] = (start, )            
    pq = [(0, path[start])]

    while pq:
        di, pathi = heapq.heappop(pq)
        v = pathi[-1]
        if v == goal:
            return di,pathi

        #辺を全部見る
        for vertex, weight in E[v].items():
            new_di = di + weight
            if (new_di < dist[vertex]) or (new_di == dist[vertex] and pathi + (vertex, ) < path[vertex]):
                dist[vertex] = new_di
                path[vertex] = pathi + (vertex, )
                heapq.heappush(pq, (new_di, path[vertex]))

class UnionFind():
    def __init__(self, n):
        self.table = [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

    def unite(self, x, y):
        # x,yの根を格納する 
        x = self.find(x)
        y = self.find(y)

        #同一グラフ内だった場合
        if x == y:
            return False

        if self.rank[x] > self.rank[y]:
            self.table[y] = x
        else:
            self.table[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


    def find(self, x):
        """ xの根の値を返すメソッド """
        #xが根である時
        if self.table[x] == x:
            return x
        #xが根でない ==> 根へたどる&根へつけかえる
        self.table[x] = self.find(self.table[x])
        #根の値を返す
        return self.table[x]

    def SameGragh(self,x,y):
        """二つの値が同一グラフ内だった場合:True,違う場合:False"""
        if self.find(x) == self.find(y):
            return True
        else:
            return False

N,M = map(int,input().split(" "))
E = [dict() for i in range(N)]
tree = UnionFind(N)
for i in range(M):
    L,R,D = map(int,input().split(" "))
    if tree.SameGragh(L-1,R-1):
        di,path = dijkstra(N,L-1,R-1,E)
        if di != D:
            print("No")
            exit(0)

    else:
        E[L-1][R-1] = D
        tree.unite(L-1,R-1)

print("Yes")