Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

Fixed submission:
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, c])
  RE[b - 1].append(a - 1)
Reachable = [[False, False] for _ in range(N)]
Q = [0]
while(Q):
  q = Q.pop(0)
  Reachable[q][0] = True
  for adj, _ in E[q]:
    if not Reachable[adj][0]:
      Q.append(adj)
Q = [N - 1]
while(Q):
  q = Q.pop(0)
  Reachable[q][1] = True
  for adj in RE[q]:
    if not Reachable[adj][1]:
      Q.append(adj)
R = [r[0] and r[1] for r in Reachable]
D = [None] * N
D[0] = 0
for _ in range(N):
  for s in range(N):
    if D[s] == None:
      continue
    for adj, coin in E[s]:
      if not R[adj]:
        continue
      if D[adj] == None:
        D[adj] = D[s] + coin - P
      else:
        D[adj] = max(D[adj], D[s] + coin - P)
for s in range(N):
  if D[s] == None:
    continue
  for adj, coin in E[s]:
    if not R[adj]:
      continue
    if D[adj] == None:
      continue
    elif D[adj] < D[s] + coin - P:
      D[-1] = None
if D[-1] == None:
  print(-1)
else:
  print(max(D[-1], 0))

Fixed submission:
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, c])
  RE[b - 1].append(a - 1)
Reachable = [[False, False] for _ in range(N)]
Q = [0]
while(Q):
  q = Q.pop(0)
  Reachable[q][0] = True
  for adj, _ in E[q]:
    if not Reachable[adj][0]:
      Q.append(adj)
Q = [N - 1]
while(Q):
  q = Q.pop(0)
  Reachable[q][1] = True
  for adj in RE[q]:
    if not Reachable[adj][1]:
      Q.append(adj)
R = [r[0] and r[1] for r in Reachable]
D = [None] * N
D[0] = 0
for _ in range(N):
  for s in range(N):
    if D[s] == None:
      continue
    for adj, coin in E[s]:
      if not R[adj]:
        continue
      if D[adj] == None:
        D[adj] = D[s] + coin - P
      else:
        D[adj] = max(D[adj], D[s] + coin - P)
for s in range(N):
  if D[s] == None:
    continue
  for adj, coin in E[s]:
    if not R[adj]:
      continue
    if D[adj] == None:
      continue
    elif D[adj] < D[s] + coin - P:
      D[-1] = None
if D[-1] == None:
  print(-1)
else:
  print(max(D[-1], 0))

Fixed submission:
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

Buggy python submission (verdict: Runtime Error):
N, M, P = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, c])
  RE[b - 1].append(a - 1)
Reachable = [[False, False] for _ in range(N)]
Q = [0]
while(Q):
  q = Q.pop(0)
  Reachable[q][0] = True
  for adj, _ in E[q]:
    if not Reachable[adj][0]:
      Q.append(adj)
Q = [N - 1]
while(Q):
  q = Q.pop(0)
  Reachable[q][1] = True
  for adj in RE[q]:
    if not Reachable[adj][1]:
      Q.append(adj)
R = [r[0] and r[1] for r in Reachable]
C = [None] * N
C[0] = 0
A = [0, 0]
def DFS(s):
  if A[1] != 0:
    return 0
  if s == N - 1:
    A[0] = max(C[s], A[0])
  for adj, coin in E[s]:
    if not R[s]:
      continue
    if C[adj] == None:
      C[adj] = C[s] + coin - P
      DFS(adj)
      C[adj] = None
    elif C[adj] < C[s] + coin - P:
      A[1] = -1
      return 0
DFS(0)
if A[1] != 0:
  print(-1)
else:
  print(A[0])

Fixed submission:
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))