Buggy python submission (verdict: Time Limit Exceeded):
n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))


Fixed submission:
n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m,p = map(int, input().split())
edge = []
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
for i in range(n-1):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
ant1 = max(-dis[n],0)
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
ant2 = max(-dis[n],0)
if ant1 != ant2:
  print(-1)
else:
  print(ant1)

Fixed submission:
n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m,p = map(int, input().split())
edge = []
ren = [set([i]) for i in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    ren[b] |= ren[a]
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
for v in t:
  if v in ren[n]:
    print(-1)
    break
else:
  print(max(0,-dis[n]))

Fixed submission:
n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))

Buggy python submission (verdict: Time Limit Exceeded):
n,m,p = map(int, input().split())
edge = []
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
if not t:
  print(max(0,-dis[n]))
else:
  redu = [0]*(n+1)
  for v in t:
    redu[v] = 1
  for i in range(n-1):
    for a,b,c in edge:
      if dis[b] > dis[a] + c:
        dis[b] = dis[a] + c
        redu[b] |= redu[a]
    if redu[n]:
      print(-1)
      break
  else:
    print(max(0,-dis[n]))


Fixed submission:
n,m,p = map(int, input().split())
edge = []
e1 = [list() for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int, input().split())
  edge.append((a,b,p-c))
  e1[a].append(b)
dis = [float("inf")]*(n+1)
dis[1] = 0
t = []
for i in range(n):
  for a,b,c in edge:
    if dis[b] > dis[a] + c:
      dis[b] = dis[a] + c
      if i == n-1:
        t.append(b)
s = set(t)
while t:
  v = t.pop()
  for x in e1[v]:
    if x == n:
      print(-1)
      exit(0)
    if x in s:
      continue
    s.add(x)
    t.append(x)
print(max(0,-dis[n]))