Buggy python submission (verdict: Time Limit Exceeded):
# n, m, p = map(int, input().split())
 
# n, m, p = 4, 5, 10
# arr = [[1, 2, 1], [1, 4, 1], [3, 4, 1], [2, 2, 100], [3, 3, 100]]

# n, m, p = 2, 2, 10
# arr = [(1, 2, 100), (2, 2, 100)]

n, m, p = map(int, input().split())
# arr = [(1, 2, 20), (2, 3, 30), (1, 3, 45)]

# n, m, p = 3, 4, 99999
# arr= [(1, 3, 8), (3, 2, 10), (2, 2, 100000), (2, 1, 3)]

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, input().split())
	abc.append((a-1, b-1, p-c))
	rev_edge[b-1].append(a-1)

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))

Fixed submission:
import sys

n, m, p = map(int, sys.stdin.readline().split())

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, sys.stdin.readline().split())
	abc.append((a-1, b-1, p-c))
	rev_edge[b-1].append(a-1)

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))

Buggy python submission (verdict: Time Limit Exceeded):

n, m, p = map(int, input().split())
arr = [0]*(m)
for i in range(m):
	arr[i] = tuple(map(int, input().split()))
# n, m, p = 4, 5, 10
# arr = [[1, 2, 1], [1, 4, 1], [3, 4, 1], [2, 2, 100], [3, 3, 100]]

# n, m, p = 2, 2, 10
# arr = [(1, 2, 100), (2, 2, 100)]

# n, m, p = 3, 3, 10
# arr = [(1, 2, 20), (2, 3, 30), (1, 3, 45)]

dist = [float('inf')]*(n+1)

dist[1] = 0
parent = [-1]*(n+1)
for k in range(n-1):
	for i in range(m):
		u, v, c = arr[i]
		c = max(c-p, 0)
		if dist[u] - c < dist[v]:
			dist[v] = dist[u] - c
			if v != u: parent[v] = u
path = []
end = n
while parent[end] != -1:
	path.append(end)
	end = parent[end]
# print(parent)	
# print(dist)
path.append(1)
path.reverse()
old_dist = list(dist)

for i in range(m):
	u, v, c = arr[i]
	c = max(c-p, 0)
	if old_dist[u] - c < dist[v]:
		old_dist[v] = old_dist[u] - c
# print(old_dist)
for ele in path:
	if old_dist[ele] != dist[ele]:
		neg_cycle = True
		break
	neg_cycle = False

if neg_cycle:
	print(-1)
else:
	print(-1 if n not in path else -dist[n])

Fixed submission:
import sys

n, m, p = map(int, sys.stdin.readline().split())

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, sys.stdin.readline().split())
	abc.append((a-1, b-1, p-c))
	rev_edge[b-1].append(a-1)

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))