Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					#negative cycle
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b,c in zip(*[iter(L)]*3):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
		tmp[a-1].append((b-1,P-c))
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,es in enumerate(tmp):
		if a not in judge:
			continue
		for b,c in es:
			if b in judge:
				G[a].append((b,c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()


Fixed submission:
n,m,p = map(int,input().split())
graph = [[] for _ in range(n)]
INF = float("inf")
dist = [INF]*n
dist[0] = 0

for _ in range(m):
	f,t,c = map(int,input().split())
	graph[f-1].append((t-1,p-c))
#print(graph)

for _ in range(n):
	update = False
	for f,e in enumerate(graph):
		for t,c in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
	for _ in range(n):
		update = False
		for f,e in enumerate(graph):
			for t,c in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = dist[f] + c
					update = True
		if not update:
			break
	if dist[-1] != prev:
		print(-1)
		exit()
#print(dist)

print(max(0,dist[-1]*(-1)))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def reachable(es, source):
	ret = {source}
	Q = deque([source])
	while Q:
		cur = Q.popleft()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					#negative cycle
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b in zip(L[::3],L[1::3]):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,b,c in zip(*[iter(L)]*3):
		if a-1 in judge and b-1 in judge:
			G[a-1].append((b-1,P-c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

Fixed submission:
n,m,p = map(int,input().split())
graph = [[] for _ in range(n)]
INF = float("inf")
dist = [INF]*n
dist[0] = 0

for _ in range(m):
	f,t,c = map(int,input().split())
	graph[f-1].append((t-1,p-c))
#print(graph)

for _ in range(n):
	update = False
	for f,e in enumerate(graph):
		for t,c in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
	for _ in range(n):
		update = False
		for f,e in enumerate(graph):
			for t,c in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = dist[f] + c
					update = True
		if not update:
			break
	if dist[-1] != prev:
		print(-1)
		exit()
#print(dist)

print(max(0,dist[-1]*(-1)))

Buggy python submission (verdict: Runtime Error):
n,m,p = map(int,input().split())
graph = [[] for _ in range(n)]
INF = float("inf")
dist = [INF]*n
dist[0] = 0

for _ in range(m):
	f,t,c = map(int,input().split())
	graph[f-1].append((t-1,p-c))
#print(graph)

for _ in range(n):
	update = False
	for f,e in enumerate(graph):
		for t,c in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
    for _ in range(n):
		for f,e in enumerate(graph):
			for t,c in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = -INF
	if dist[-1] != prev:
		print(-1)
		exit()
#print(dist)

print(max(0,dist[-1]*(-1)))

Fixed submission:
n,m,p = map(int,input().split())
graph = [[] for _ in range(n)]
INF = float("inf")
dist = [INF]*n
dist[0] = 0

for _ in range(m):
	f,t,c = map(int,input().split())
	graph[f-1].append((t-1,p-c))
#print(graph)

for _ in range(n):
	update = False
	for f,e in enumerate(graph):
		for t,c in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
	for _ in range(n):
		update = False
		for f,e in enumerate(graph):
			for t,c in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = dist[f] + c
					update = True
		if not update:
			break
	if dist[-1] != prev:
		print(-1)
		exit()
#print(dist)

print(max(0,dist[-1]*(-1)))