Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N
used = [False] * N


def dfs(u):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w)


def dfs2(u, dest):
    dfs(u)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    used = [False] * N
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        if not check[e]:
            continue
        for w, c in G[e]:
            if not check[w]:
                continue
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))




Fixed submission:
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N


def dfs(u, used):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w, used)


def dfs2(u, dest):
    used = [False] * N
    dfs(u, used)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        if not check[e]:
            continue
        for w, c in G[e]:
            if not check[w] or dist[e] == INF:
                continue
            if dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))

Fixed submission:
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N


def dfs(u, used):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w, used)


def dfs2(u, dest):
    used = [False] * N
    dfs(u, used)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        for w, c in G[e]:
            if not check[e] or not check[w] or dist[e] == INF:
                continue
            if dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))

Fixed submission:
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit((10 ** 6))
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N


def dfs(u, used):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w, used)


def dfs2(u, dest):
    used = [False] * N
    dfs(u, used)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        for w, c in G[e]:
            if not check[e] or not check[w] or dist[e] == INF:
                continue
            if dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))







Fixed submission:
import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))