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: Time Limit Exceeded

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
                    
for i in range(1, N+1):
    if d[i] == 10**9:
        f(i, 0)
    else:
        f(i, d[i])
if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

n,m = map(int,input().split())
e = []
for i in range(n+1):
  e.append([])

for i in range(m):
  l,r,d = map(int,input().split())
  e[l].append([r,d])
  e[r].append([l,-d])
#print(e)

c = [0]*(n+1) #チェック用
p = [0]*(n+1) #位置

flag = True
k = 1
while k < n:
  if c[k] == 2:
    k += 1
    continue
  q = Queue()
  q.put(k)
  p[k] = 0
  c[k] = 1
  while not q.empty():
    x = q.get()
    c[x] = 2
    for t in e[x]:
      y = t[0]
      d = t[1]
      if c[y] == 0:
        p[y] = p[x] + d
        c[y] = 1
        q.put(y)
      elif c[y] == 1:
        if not p[y] == p[x] + d:
          print("No")
          quit()
      else:
        w = 1
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]

up = [ set([]) for i in range(N)]
dw = [ set([]) for i in range(N)]

for l,r,d in li:
  dw[l-1].add(r-1)
  up[r-1].add(l-1)

S = []
for n in range(N):
  if ( len(up[n])==0 ):
    S.append(n)
L = []
for i in range(N+M):

  if ( len(S)==0 ):
    break
  n = S.pop()
  L.append(n)
  for r in dw[n]:
    up[r].discard(n)
    if ( len(up[r]) == 0 ):
      S.append(r)
  dw[n]=set()

BREAK=False
if (sum([len(s) for s in up])>0):
    BREAK=True

dwl = [ set([]) for i in range(N)]
for l,r,d in li:
  dwl[l-1].add((r-1,d))

dis = [-1]*N

for n in L:
  if (BREAK):
    break
  if (dis[n]==-1):
    dis[n]=0
  for r,d in dwl[n]:
    if (dis[r]==-1):
        dis[r]=dis[n]+d
    else:
        if not (dis[r]==dis[n]+d):
            BREAK=True
            break
if (BREAK):
    print ("No")
else:
    print ("Yes")

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
from collections import defaultdict
from Queue import Queue
import sys
N,M=map(int,sys.stdin.readline().split())
L=[None]*200001
R=[None]*200001
D=[None]*200001
C=defaultdict(list)
done=[False]*200001
if M==0:
    print("Yes")
    sys.exit(0)

class UnionFind(object):
    #https://www.kumilog.net/entry/union-find
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

uf=UnionFind(n=N+1)
for i in xrange(M):
    l,r,d=map(int,sys.stdin.readline().split())
    L[i]=l
    R[i]=r
    D[i]=d
    C[l].append(i);C[r].append(i)
    uf.union(l,r)
groups={}
for i in range(1,N+1):
    groups[uf.find(i)]=i

X=[None]*200001
for group in groups:
    Q=Queue()
    X[group]=0
    for c in C[group]:
        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: Time Limit Exceeded

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
if M==0:
    print("Yes")
    sys.exit(0)

class UnionFind(object):
    #https://www.kumilog.net/entry/union-find
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

uf=UnionFind(n=N+1)
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)
    uf.union(l,r)
groups={}
for i in range(1,N+1):
    groups[uf.find(i)]=i

X=[None]*200001
for group in groups:
    Q=Queue()
    X[group]=0
    for c in C[group]:
        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: Time Limit Exceeded

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 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])
    
    for i in range(M):
        if done[i] is not None and not done[i]:
            for c in C[i]:
                Q.put(c);done[c]=True
            break
    else:
        break 


print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class WeightedUnionFind:
    def __init__(self, nodes):
        """
        :param collections.Iterable nodes:
        """
        self._parents = {k: k for k in nodes}
        self._ranks = {k: 0 for k in nodes}
        self._sizes = {k: 1 for k in nodes}
        # 直近の親からの重み。root なら 0
        self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        # それぞれの root をくっつけたいので root 間の重みに変換
        # x が上、y が下
        w += self.weight(x)
        w -= self.weight(y)

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
            self._weights[x] = 0
            self._weights[y] = w
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            self._weights[x] = -w
            self._weights[y] = 0
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self.weight(y) - self.weight(x)
        return float('inf')


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

uf = WeightedUnionFind([i + 1 for i in range(N)])
ok = True
for _ in range(M):
    l, r, d = list(map(int, input().split()))
    if uf.find(l) == uf.find(r) and uf.diff(l, r) != d:
        ok = False
        break
    uf.unite(l, r, d)

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

ans = True
n = [None] * N
q = []
n0 = 0
while ans:
    n[n0] = 0
    q.append(n0)
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
            elif n[j]-n[i] != d:
                ans = False
                break
        if not ans:
            break
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

n = [None] * N
q = []
n0 = 0
while 1:
    n[n0] = 0
    q.append(n0)
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

ans = True
for L,R,D in LRD:
    if n[R]-n[L]!= D:
        ans = False
        break
if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(65536)

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

path=[[] for _ in range(N+1)]

for _ in range(M):
	l,r,d=map(int, input().split())
	path[l].append((r,+d))
	path[r].append((l,-d))

cost=[None for _ in range(N+1)]

def dfs(i, c):
	if cost[i] is None:
		cost[i] = c
		for j,d in path[i]:
			if not dfs(j, c+d):
				return False
	return cost[i] == c

ans = "Yes"

for i in range(1, N+1):
	if cost[i] is None and not dfs(i, 0):
		ans = "No"
		break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
LRD = (map(int, input().split()) for _ in range(M))

DDD = [[None] * N for _ in range(N)]

res = True
for ll, rr, dd in LRD:
  if ll < rr:
    l, r = ll-1, rr-1
    d = dd
  else:
    l, r = rr-1, ll-1
    d = -dd
  if DDD[l][r] is None:
    DDD[l][r] = d
    for i in range(N):
      if i < r and DDD[i][r] is not None:
        DDD[l][i] = d - DDD[i][r]
      if r < i and DDD[r][i] is not None:
        DDD[l][i] = d + DDD[r][i]
      if i < l and DDD[i][l] is not None:
        DDD[i][r] = d + DDD[i][l]
      if l < i and DDD[l][i] is not None:
        DDD[i][r] = d - DDD[l][i]
  else:
    if DDD[l][r] != d:
      res = False
      break
print(res and 'Yes' or 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
LRD = (map(int, input().split()) for _ in range(M))

DDD = [[None] * N for _ in range(N)]

res = True
for l, r, d in LRD:
  l -= 1
  r -= 1
  if DDD[l][r] is None:
    DDD[l][r] = d
    DDD[r][l] = -DDD[l][r]
    for i in range(N):
      if DDD[r][i] is not None:
        DDD[l][i] = d + DDD[r][i]
        DDD[i][l] = -DDD[l][i]
      if DDD[i][l] is not None:
        DDD[i][r] = d + DDD[i][l]
        DDD[r][i] = -DDD[i][r]
  else:
    if DDD[l][r] != d:
      res = False
      break
print(res and 'Yes' or 'No')

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

def trav(i):
    global g
    global v
    global v_asn
    global f
    for a in g[i]:
        if not v_asn[a[0]]:
            v_asn[a[0]] = True
            v[a[0]] = v[i] + a[1]
            trav(a[0])
        else:
            if v[a[0]] != v[i] + a[1]:
                f = False
                return

for i in range(1, n + 1):
    if not v_asn[i]:
        v_asn[i] = True
        trav(i)
        if not f:
            break

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

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def d2r(x):
    global par
    global d2p
    k = x
    s = 0
    while k != par[k]:
        s += d2p[k]
        k = par[k]
    return s

def root(x):
    global par
    global d2p
    #print(par, d2p)
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        s = d2r(x)
        par[x] = r
        d2p[x] = s
        return r


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx = root(x)
    dx = d2r(x)
    ry = root(y)
    dy = d2r(y)
    if rx != ry:
        par[rx] = ry
        d2p[rx] = dy + d - dx
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * m
r = [0] * m
d = [0] * m

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

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

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def root(x):
    global par
    global d2p
    if par[x] == x:
        return (x, 0)
    else:
        r = root(par[x])
        par[x] = r[0]
        d2p[x] += r[1]
        #print(par, d2p)
        return (r[0], d2p[x])


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx, dx = root(x)
    ry, dy = root(y)
    if rx != ry:
        par[rx] = ry
        d2p[rx] = dy + d - dx
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * m
r = [0] * m
d = [0] * m

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

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

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def root(x):
    global par
    global d2p
    if par[x] == x:
        return (x, 0)
    else:
        r = root(par[x])
        par[x] = r[0]
        d2p[x] += r[1]
        #print(par, d2p)
        return (r[0], d2p[x])


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx, dx = root(x)
    ry, dy = root(y)
    if rx != ry:
        par[rx] = ry
        d2p[rx] = dy + d - dx
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * m
r = [0] * m
d = [0] * m

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

if f and max(d2p) <= 10**9:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(branch,arrival,start):
    q = deque([start])
    arrival[start] = 0
    check = True
    while len(q) != 0 and check:
        nextpoint = branch[q[0]]
        for i in range(len(nextpoint)):
            if arrival[nextpoint[i][0]] == None:
                arrival[nextpoint[i][0]] = arrival[q[0]] + nextpoint[i][1]
                q.append(nextpoint[i][0])
            else:
                if arrival[nextpoint[i][0]] != arrival[q[0]] + nextpoint[i][1]:
                    check = False
        q.popleft()
    if check:
        return True
    else:
        return False


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

arrival = [None for i in range(n+1)]
a = 0
for i in range(1,n+1):
    if arrival[i] == None:
        temp = bfs(branch,arrival,i)
        if temp == False:
            a = 1
            print("No")
            break
if a == 0:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def bfs(branch,arrival,start):
    q = [start]
    arrival[start] = 0
    check = True
    while len(q) != 0 and check:
        nextpoint = branch[q[0]]
        for i in range(len(nextpoint)):
            if arrival[nextpoint[i][0]] == None:
                arrival[nextpoint[i][0]] = arrival[q[0]] + nextpoint[i][1]
                q.append(nextpoint[i][0])
            else:
                if arrival[nextpoint[i][0]] != arrival[q[0]] + nextpoint[i][1]:
                    check = False
        q.pop(0)
    if check:
        return True
    else:
        return False


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

arrival = [None for i in range(n+1)]
a = 0
for i in range(1,n+1):
    if arrival[i] == None:
        temp = bfs(branch,arrival,i)
        if temp == False:
            a = 1
            print("No")
            break
if a == 0:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def bfs(branch,arrival,start):
    q = [start]
    arrival[start] = 0
    check = True
    while len(q) != 0 and check:
        nextpoint = branch[q[0]]
        for i in range(len(nextpoint)):
            if arrival[nextpoint[i][0]] == False:
                arrival[nextpoint[i][0]] = arrival[q[0]] + nextpoint[i][1]
                q.append(nextpoint[i][0])
            else:
                if arrival[nextpoint[i][0]] != arrival[q[0]] + nextpoint[i][1]:
                    check = False
        q.pop(0)
    if check:
        return True
    else:
        return False


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

arrival = [False for i in range(n+1)]
a = 0
for i in range(1,n+1):
    if arrival[i] == False:
        temp = bfs(branch,arrival,i)
        if temp == False:
            a = 1
            print("No")
            break
if a == 0:
    print("Yes")

Submission status: Time Limit Exceeded

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

data =[0]
access = [False]*(n+1)
dis = [0]+[" "]*(n)
q = queue.Queue()
for i in range(n):
    data.append([])

for i in range(m):
    l,r,d = map(int,input().split())

    data[l].append((r,d))
    data[r].append((l,-d))

for i in range(1,n+1):
    data[i].sort(reverse=True)

for i in range(1,n+1):
    if data[i]!=[] and not access[i]: 
        q.put(i)
        access[i] = True
        dis[i] = 0
        while not q.empty():
            l = q.get()

            while data[l]:
                r,d = data[l].pop()
                if access[r]:
                    if dis[r] ==dis[l]+d:
                        continue
                    else:
                        print("No")
                        exit(0)
                else:
                    access[r] = True
                    dis[r] = dis[l]+d
                    q.put(r)
print("Yes")

Submission status: Time Limit Exceeded

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

data =[0]
access = [False]*(n+1)
dis = [0]+[" "]*(n)
q = queue.Queue()
for i in range(n):
    data.append([])

for i in range(m):
    l,r,d = map(int,input().split())

    data[l].append((r,d))
    data[r].append((l,-d))

for i in range(1,n+1):
    data[i].sort(reverse=True)

for i in range(1,n+1):
    if data[i]!=[] and not access[i]: 
        q.put(i)
        access[i] = True
        dis[i] = 0
        while not q.empty():
            l = q.get()

            for r,d in data[l]:
                if access[r]:
                    if dis[r] ==dis[l]+d:
                        continue
                    else:
                        print("No")
                        exit(0)
                else:
                    access[r] = True
                    dis[r] = dis[l]+d
                    q.put(r)
print("Yes")

Submission status: Time Limit Exceeded

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    p = parent(tree[n][0])
    if p[0] == tree[n][0]:
        return tree[n]
    d = distance_to_root(n)
    tree[n][0] = p[0]
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    ret = 0
    nn = n
    while tree[nn] is not None:
        ret += tree[nn][1]
        nn = tree[nn][0]
    return ret

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")

Submission status: Time Limit Exceeded

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    d = distance_to_root(n)
    p = parent(tree[n][0])
    tree[n][0] = p[0]
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    if tree[n] is None:
        return 0
    d = distance_to_root(tree[n][0])
    return d + tree[n][1]

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")

Submission status: Time Limit Exceeded

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    d = distance_to_root(n)
    p = parent(tree[n][0])
    if p[0] == tree[n][0]:
        return tree[n]
    pp = [p[0], d]
    tree[n] = pp
    return pp

def distance_to_root(n):
    if tree[n] is None:
        return 0
    d = distance_to_root(tree[n][0])
    return d + tree[n][1]

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")

Submission status: Time Limit Exceeded

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    d = distance_to_root(n)
    p = parent(tree[n][0])
    pp = [p[0], d]
    tree[n] = pp
    return pp

def distance_to_root(n):
    if tree[n] is None:
        return 0
    d = distance_to_root(tree[n][0])
    return d + tree[n][1]

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")