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())

l, r, d = [], [], []

for i in range(m):
    l_, r_, d_ = map(int, input().split())
    if l_ < r_:
        l.append(l_-1)
        r.append(r_-1)
        d.append(d_)
    else:
        l.append(r_-1)
        r.append(l_-1)
        d.append(-d_)

import numpy as np
arg = np.argsort(l)

l, r, d = np.array(l)[arg], np.array(r)[arg], np.array(d)[arg]
p = [None for i in range(n)]

def solve():

    if m == 0:
        print("Yes")
        return
    
    for i in range(m):
        if p[l[i]] is None and p[r[i]] is None:
            # initialize
            p[l[i]] = 0
            p[r[i]] = d[i]
        elif p[l[i]] is None:
            # add rule
            p[l[i]] = p[r[i]] - d[i]
        elif p[r[i]] is None:
            # add rule
            p[r[i]] = p[l[i]] + d[i]
        else:
            # check rule
            if p[r[i]] - p[l[i]] != d[i]:
                print("No")
                return

    # check max position
    if max(p) > 10**9:
        print("No")
    else:
        print("Yes")

solve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
loc = [float('inf')] * (N + 1)
ok = True
for _ in range(M):
    L, R, D = map(int, input().split())
    if loc[L] < float('inf'):
        if loc[R] < float('inf'):
            if loc[R] - loc[L] != D:
                ok = False
                # print(L, R, D)
                # print(loc[L], loc[R], D)
                break
            else:
                pass
        else:
            loc[R] = loc[L] + D
    else:
        if loc[R] < float('inf'):
            loc[L] = loc[R] - D
        else:
            loc[L] = 0
            loc[R] = D

lend, rend = float('inf'), -float('inf')
for x in loc:
    if x == float('inf'):
        pass
    else:
        if x < lend:
            lend = x
        if x > rend:
            rend = x
span = rend - lend if M > 0 else 0
if ok:
    ok = span < 10 ** 9 + 1
# print(lend, rend, span)
print('Yes' if ok else 'No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
loc = [float('inf')] * (N + 1)
ok = True
for _ in range(M):
    L, R, D = map(int, input().split())
    if loc[L] < float('inf'):
        if loc[R] < float('inf'):
            if loc[L] + loc[R] != D:
                ok = False
                # print(L, R, D)
                # print(loc[L], loc[R], D)
                break
            else:
                pass
        else:
            loc[R] = loc[L] + D
    else:
        if loc[R] < float('inf'):
            loc[L] = loc[R] - D
        else:
            loc[L] = 0
            loc[R] = D

lend, rend = float('inf'), -float('inf')
for x in loc:
    if x == float('inf'):
        pass
    else:
        if x < lend:
            lend = x
        if x > rend:
            rend = x
span = rend - lend if M > 0 else 0
if ok:
    ok = span < 10 ** 9 + 1
# print(lend, rend, span)
print('Yes' if ok else 'No')

Submission status: Wrong Answer

Solution code:
n, m = (int(x) for x in input().split())
p = [(i,0) for i in range(n)]

def check(i):
    j, d = p[i]
    if j != i:
        ii, dd = check(j)
        p[i] = (ii, dd+d)
    return p[i]

f = True
for _ in range(m):
    l, r, d = (int(x) for x in input().split())
    l-=1;r-=1
    li, ld = check(l)
    ri, rd = check(r)
    if li != ri:
        p[ri] = (li, d+ld)
    else:
        if rd - ld != d:
            f = False
            break
print("Yes" if f else "No")

Submission status: Wrong Answer

Solution code:
#def fun():


[N,M]=map(int,raw_input().split())
A={}
B={}
for i in range(1,N+1):
    A[i]=[]
    B[i]=[]
bignum=-100000000000
C=[bignum for x in range(N+1)]
for i in range(M):
    [L,R,D]=map(int,raw_input().split())
    A[L].append([R,D])
    A[R].append([L,-D])
K=A.keys()
E=[]
flg=1
while len(K)!=0 or len(E)!=0:
    if len(E)==0:
        k=K.pop(0)
        C[k]=0
    else:
        k=E.pop(0)
    a=A[k]+B[k]
    for aa in a:
        [n,d]=aa
        if C[n]!=bignum and C[n]!=C[k]+d:
            print "No"
            flg=0
        else:
            C[n]=C[k]+d
        if n in K:
            K.remove(n)
            E.append(n)
    if not flg:
        break
    #print k,C,E
if flg:
    print "yes"
#print C

Submission status: Wrong Answer

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

right = [{} for _ in range(N)]

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

res = True

for l in range(N):
    for r, d in right[l].items():
        for s in set(right[l].keys()) & set(right[r].keys()):
            if right[l][s] != right[l][r] + right[r][s]:
                res = False

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
loc = [float('inf')] * (N + 1)
ok = True
for _ in range(M):
    L, R, D = map(int, input().split())
    if loc[L] < float('inf'):
        if loc[R] < float('inf'):
            if loc[L] + loc[R] != D:
                ok = False
                # print(L, R, D)
                # print(loc[L], loc[R], D)
                break
            else:
                pass
        else:
            loc[R] = loc[L] + D
    else:
        if loc[R] < float('inf'):
            loc[L] = loc[R] - D
        else:
            loc[L] = 0
            loc[R] = D
print('Yes' if ok else 'No')

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()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = ['s'] * n
    def g(i,c):
        if b[i] != 's' and c != 's':
            return False
        if b[i] != 's':
            if c == 's':
                return True
            return b[i] == c
        if c == 's':
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,'s'):
            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()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    r = [0] * n
    f = [False] * n
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))
        f[r-1] = False

    b = ['s'] * n
    def g(i,c):
        if f[i] and c != 's':
            return False
        if b[i] != 's':
            if c == 's':
                return True
            return b[i] == c
        if c == 's':
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,'s'):
            return 'NO'
    return 'YES'


print(main())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
il=[[] for i in range(n)]
for i in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  il[l].append((r,d))
  il[r].append((l,-d))


ed=[-1 for i in range(n)]
f=True
for i in range(n):
  if ed[i]!=-1:
    continue
  s=[i]
  while s:
    ns=[]
    for i in s:
      for j in il[i]:
        if ed[j[0]]==-1:
          ed[j[0]]=ed[i]+j[1]
          ns.append(j[0])
        else:
          if ed[j[0]]!=ed[i]+j[1]:
            f=False
            break
    s=ns
if f:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
il=[[] for i in range(n)]
for i in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  il[l].append((r,d))
  il[r].append((l,-d))


ed=[-1 for i in range(n)]
f=True
for i in range(n):
  if ed[i]!=-1:
    continue
  s=[i]
  while s:
    ns=[]
    for i in s:
      for j in il[i]:
        if ed[j[0]]==-1:
          ed[j[0]]=ed[i]+j[1]
          ns.append(j[0])
        else:
          t=ed[i]+j[1]
          if ed[j[0]]!=ed[i]+j[1]:
            f=False
            break
      if not f:
        break
    s=ns
    if not f:
      break
  if not f:
    break
if f:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(4100000)

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

dist = [int(1e10)] * N

def bfs(id):
    
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

visited = [False] * N

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

visited = [False] * N

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True
        for edge in graph[v]:
            u = edge[0]
            d = edge[1]
            if(dist[u] == int(1e10)):
                dist[u] = dist[v] + d
                Q.append(u)
            else:
                if(dist[u] != dist[v] + d):
                    print("No")
                    exit()

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

graph = [[] for i in range(N)] 

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

visited = [False] * N

for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        for edge in graph[v]:
            u = edge[0]
            d = edge[1]
            if(dist[u] == int(1e10)):
                dist[u] = dist[v] + d
                Q.append(u)
            else:
                if(dist[u] != dist[v] + d):
                    print("No")
                    exit()

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

graph = [[] for i in range(N)] 

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

visited = [False] * N

for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


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 roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
re_check = deque([])
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            print("No")
            sys.exit()
    elif l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

while re_check:
    l, r, d = re_check.popleft()
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            print("No")
            sys.exit()
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

if max(x.values()) - min(x.values()) > 10**9:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
ans = "Yes"
re_check = deque([])
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
            break
    elif l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

while re_check and ans == "Yes":
    l, r, d = re_check.popleft()
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {}
ans = "Yes"
re_check = deque([])
# 根の座標を０で確定
for i, y in enumerate(uf.parents):
    if y < 0:
        x[i] = 0

for l, r, d in graph:
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
            break
    elif l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

while re_check:
    l, r, d = re_check.popleft()
    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d
    else:
        re_check.append((l, r, d))

if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"

print(ans)

Submission status: Time Limit Exceeded

Solution 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 roots(self):
        return {i for i, x in enumerate(self.parents) if x < 0}


n, m = map(int, input().split())
graph = []
uf = UnionFind(n+1)
for _ in range(m):
    l, r, d = map(int, input().split())
    uf.union(l, r)
    graph.append((l, r, d))

x = {0: 0}
ans = "Yes"
# 根の座標を０で確定
for l, r, d in graph:
    if l in uf.roots():
        x[l] = 0

    if l in x.keys() and r in x.keys():
        if x[r] - x[l] != d:
            ans = "No"
        continue
    if l in x.keys():
        x[r] = x[l] + d
    elif r in x.keys():
        x[l] = x[r] - d


if max(x.values()) - min(x.values()) > 10**9:
    ans = "No"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5+1)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n,m=map(int,input().split())
    g=[[] for i in range(n)]
    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        g[a].append([b,c])
        g[b].append([a,-c])
    inf=10**10
    v=[inf]*n
    while max(v)==inf:
        s=v.index(inf)
        q=deque([s])
        v[s]=0
        while q:
            p=q.popleft()
            for i in g[p]:
                if v[i[0]]==inf:
                    v[i[0]]=v[p]+i[1]
                    q.append(i[0])
                else:
                    if v[i[0]]!=v[p]+i[1]:
                        return 'No'
    return 'Yes'
                            
  
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append((u, dpd))

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
vs = set()
def dfs_w(d, stack):
    depthh = [-1] + [0]*N
    path = [0]
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)
            pvs.add(v)
            depthh[v] = depthh[parent] + dpd

            for u, dpd in d[v]:
                if u in pvs:
                    if depthh[u] != depthh[v] + dpd:
                        return False
                if u in vs:
                    continue
                stack += [(-v, dpd), (u, dpd)]
        else:
            path.pop()

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")