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


def bellman_ford(start: int, graph: list) -> list:
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    INF = float("inf")
    n = len(graph)
    dist = [-INF] * n
    dist[start] = 0
    if n == 1:
        return False, [0]
    for _ in range(n - 1):
        update = False
        for v, edge in enumerate(graph):
            for nxt_v, cost in edge:
                if not (visited[nxt_v] and visited2[nxt_v]):
                    continue
                if dist[nxt_v] < dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist
    return False, dist

def bellman_ford2(start: int, graph: list) -> list:
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    INF = float("inf")
    n = len(graph)
    dist = [-INF] * n
    dist[start] = 0
    if n == 1:
        return False, [0]
    for _ in range(2 * n - 1):
        update = False
        for v, edge in enumerate(graph):
            for nxt_v, cost in edge:
                if not (visited[nxt_v] and visited2[nxt_v]):
                    continue
                if dist[nxt_v] < dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist
    return False, dist

n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
rev_graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    cost -= p
    graph[a].append((b, cost))
    rev_graph[b].append((a, cost))

visited = [False] * n
def dfs():
    q = deque([0])
    visited[0] = True
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            q.append(nxt_v)
dfs()

visited2 = [False] * n
def dfs2():
    q = deque([n - 1])
    visited2[n - 1] = True
    while q:
        v = q.pop()
        for nxt_v, _ in rev_graph[v]:
            if visited2[nxt_v]:
                continue
            visited2[nxt_v] = True
            q.append(nxt_v)
dfs2()

#print(visited)
#print(visited2)

boolian, dist = bellman_ford(0, graph)
boolian, dist2 = bellman_ford2(0, graph)
if not boolian:
    print(max(dist[-1], 0))
else:
    for i in range(n):
        if dist[i] < dist2[i]:
            print(-1)
            exit()
    print(dist2[-1])
        

Fixed submission:
from collections import deque


def bellman_ford(start: int, goal: int, graph: list) -> list:
    '''bellman-ford法: 始点startから終点goalへの最小コストを求める
    重み付きグラフgraphは隣接リストで与えられる
    辺のコストは負でも良い
    負閉路検出: 始点startから終点goal上のパスに負閉路があるときは[-1]を返す
    計算量: O(|E||V|)
    '''
    INF = float("inf")
    n = len(graph)

    # スタートからゴールに到着可能かどうか判定する
    is_reachable = [False] * n
    is_reachable[start] = True
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, _ in graph[pos]:
            if is_reachable[next_pos]:
                continue
            is_reachable[next_pos] = True
            q.append(next_pos)

    # 逆辺で構築したグラフでゴールからスタートに到着可能かどうか判定する
    reverse_graph = [[] for i in range(n)]
    for pos, edge in enumerate(graph):
        for next_pos, cost in edge:
            reverse_graph[next_pos].append((pos, cost))

    is_rev_reachable = [False] * n
    is_rev_reachable[goal] = True
    q = deque([goal])
    while q:
        pos = q.popleft()
        for next_pos, _ in reverse_graph[pos]:
            if is_rev_reachable[next_pos]:
                continue
            is_rev_reachable[next_pos] = True
            q.append(next_pos)            

    need = [False] * n
    for i in range(n):
        need[i] = is_reachable[i] and is_rev_reachable[i]

    distance = [INF] * n
    distance[start] = 0
    for _ in range(n):
        is_updated = False
        for pos, edge in enumerate(graph):
            for next_pos, cost in edge:
                if not need[pos]:
                    continue
                if distance[pos] != INF and distance[pos] + cost < distance[next_pos]:
                    distance[next_pos] = distance[pos] + cost
                    is_updated = True
        if not is_updated:
            return distance[goal]
    # 負閉路が存在する
    return -INF


n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b, c = info[i]
    graph[a - 1].append((b - 1, -(c - p)))
ans = bellman_ford(0, n-1, graph)
if ans == -float("inf"):
    print(-1)
else:
    print(max(-ans, 0))

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


def bellman_ford(start: int, goal: int, graph: list) -> list:
    '''bellman-ford法: 始点startから終点goalへの最小コストを求める
    重み付きグラフgraphは隣接リストで与えられる
    辺のコストは負でも良い
    計算量: O(|E||V|)
    '''
    INF = float("inf")
    n = len(graph)

    # スタートからゴールに到着可能かどうか判定する
    is_reachable = [False] * n
    is_reachable[start] = True
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, _ in graph[pos]:
            if is_reachable[next_pos]:
                continue
            is_reachable[next_pos] = True
            q.append(next_pos)

    # 逆辺で構築したグラフでゴールからスタートに到着可能かどうか判定する
    reverse_graph = [[] for i in range(n)]
    for pos, edge in enumerate(graph):
        for next_pos, cost in edge:
            reverse_graph[next_pos].append((pos, cost))
    is_rev_reachable = [False] * n
    is_rev_reachable[goal] = True
    q = deque([goal])
    while q:
        pos = q.popleft()
        for next_pos, _ in reverse_graph[pos]:
            if is_rev_reachable[next_pos]:
                continue
            is_rev_reachable[next_pos] = True
            q.append(next_pos)            

    need = [False] * n
    for i in range(n):
        need[i] = is_reachable[i] and is_rev_reachable[i]

    distance = [INF] * n
    distance[start] = 0
    for _ in range(n):
        is_updated = False
        for pos, edge in enumerate(graph):
            for next_pos, cost in edge:
                if not need[pos]:
                    continue
                if distance[pos] != INF and distance[pos] + cost < distance[next_pos]:
                    distance[next_pos] = distance[pos] + cost
                    is_updated = True
        if not is_updated:
            return distance
    # 負閉路が存在する
    return [-INF]


n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b, c = info[i]
    graph[a - 1].append((b - 1, -(c - p)))
ans = bellman_ford(0, n-1, graph)[-1]
if ans == -float("inf"):
    print(-1)
else:
    print(max(-ans, 0))


Fixed submission:
from collections import deque


def bellman_ford(start: int, goal: int, graph: list) -> list:
    '''bellman-ford法: 始点startから終点goalへの最小コストを求める
    重み付きグラフgraphは隣接リストで与えられる
    辺のコストは負でも良い
    負閉路検出: 始点startから終点goal上のパスに負閉路があるときは[-1]を返す
    計算量: O(|E||V|)
    '''
    INF = float("inf")
    n = len(graph)

    # スタートからゴールに到着可能かどうか判定する
    is_reachable = [False] * n
    is_reachable[start] = True
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, _ in graph[pos]:
            if is_reachable[next_pos]:
                continue
            is_reachable[next_pos] = True
            q.append(next_pos)

    # 逆辺で構築したグラフでゴールからスタートに到着可能かどうか判定する
    reverse_graph = [[] for i in range(n)]
    for pos, edge in enumerate(graph):
        for next_pos, cost in edge:
            reverse_graph[next_pos].append((pos, cost))

    is_rev_reachable = [False] * n
    is_rev_reachable[goal] = True
    q = deque([goal])
    while q:
        pos = q.popleft()
        for next_pos, _ in reverse_graph[pos]:
            if is_rev_reachable[next_pos]:
                continue
            is_rev_reachable[next_pos] = True
            q.append(next_pos)            

    need = [False] * n
    for i in range(n):
        need[i] = is_reachable[i] and is_rev_reachable[i]

    distance = [INF] * n
    distance[start] = 0
    for _ in range(n):
        is_updated = False
        for pos, edge in enumerate(graph):
            for next_pos, cost in edge:
                if not need[pos]:
                    continue
                if distance[pos] != INF and distance[pos] + cost < distance[next_pos]:
                    distance[next_pos] = distance[pos] + cost
                    is_updated = True
        if not is_updated:
            return distance[goal]
    # 負閉路が存在する
    return -INF


n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b, c = info[i]
    graph[a - 1].append((b - 1, -(c - p)))
ans = bellman_ford(0, n-1, graph)
if ans == -float("inf"):
    print(-1)
else:
    print(max(-ans, 0))