Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, P = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c + P))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    self.b = pow(10, 10)
    for k in e.keys():
      for t in e[k]:
        self.edges.append(k * pow(b, 2) + t[0] * b + t[1])
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    b = self.b
    for i in range(self.n + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
    return d[t]
  def path_findloop(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    first = 0
    b = self.b
    for i in range(1, self.n * 2 + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        print(u, v, c)
        if u != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i > N: d[v] = -float("inf")
      if i == self.n:
        first = d[t] + 0
      elif i == self.n * 2:
        if first != d[t]:
          return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path_findloop(1, N)
print(res)
if res == "-loop": print(-1)
else: print(max(0, -res))

Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, P = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c + P))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    for k in e.keys():
      for t in e[k]:
        self.edges.append((k, t[0], t[1]))
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    for i in range(self.n + 1):
      for (u, v, c) in self.edges:
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
    return d[t]
  def path_findloop(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    first = 0
    for i in range(1, self.n * 2 + 1):
      for (u, v, c) in self.edges:
        if u != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i > N: d[v] = -float("inf")
      if i == self.n:
        first = d[t] + 0
      elif i == self.n * 2:
        if first != d[t]:
          return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path_findloop(1, N)
if res == "-loop": print(-1)
else: print(max(0, -res))

Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Buggy python submission (verdict: Time Limit Exceeded):
import collections
import sys
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))




Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if visited[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
Q = collections.deque([])
Q.append(1)
while Q:
  n = Q.popleft()
  visited[n] = 1
  for o in e[n]:
    if visited[o[0]] == 0:
      if o[1] + earn[n] - P > earn[o[0]]:
        Q.append(o[0])
        earn[o[0]] = o[1] + earn[n] - P
    else:
      if earn[o[0]] < o[1] + earn[n] - P:
        if isConnected(o[0]) == True:
          print(-1)
          exit(0)
  visited[n] = 0
print(max(earn[N], 0))



Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if visited[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
Q = collections.deque([])
Q.append(1)
while Q:
  n = Q.popleft()
  visited[n] = 1
  for o in e[n]:
    if visited[o[0]] == 0:
      Q.append(o[0])
      earn[o[0]] = max(o[1] + earn[n] - P, earn[o[0]])
    else:
      if earn[o[0]] < o[1] + earn[n] - P:
        if isConnected(o[0]) == True:
          print(-1)
          exit(0)
  visited[n] = 0
print(max(earn[N], 0))

Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if visited[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
Q = collections.deque([])
Q.append(1)
while Q:
  n = Q.popleft()
  visited[n] = 1
  for o in e[n]:
    if visited[o[0]] == 0:
      Q.append(o[0])
      earn[o[0]] = max(o[1] + earn[n] - P, earn[o[0]])
    else:
      if earn[o[0]] < o[1] + earn[n] - P:
        if isConnected(o[0]) == True:
          print(-1)
          exit(0)
  visited[n] = 0
print(max(earn[N], 0))

Fixed submission:
import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))