Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]
E = []
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    E.append((fr, to, -(c - P)))
    edges[fr].append(to)
    edgesR[to].append(fr)

def dfs(edges, s):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        for to in edges[st.pop()]:
            if not visited[to]:
                st.append(to)
                visited[to] = True
    return visited

canGo = dfs(edges, 0)
canBack = dfs(edgesR, N - 1)

minDist = [10**18] * N
minDist[0] = 0
for i in range(N + 1):
    for fr, to, c in E:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N and canGo[fr] and canBack[to]:
                print('-1')
                exit()
            minDist[to] = d

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


Fixed submission:
N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

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

Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())

edges = []
toE = [[] for _ in range(N)]
frE = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    toE[fr].append(to)
    frE[to].append(fr)

def getVisitedList(s, edges):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        now = st.pop()
        for to in edges[now]:
            if not visited[to]:
                visited[to] = True
                st.append(to)
    return visited

canGo = getVisitedList(0, toE)
canBack = getVisitedList(N - 1, frE)

def sol():
    minDist = [10**18] * N
    minDist[0] = 0
    for i in range(N + 1):
        for fr, to, c in edges:
            d = minDist[fr] + c
            if minDist[to] > d:
                if i == N and canGo[fr] and canBack[to]:
                    return -1
                minDist[to] = d
    return max(0, -minDist[N - 1])

print(sol())


Fixed submission:
N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

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

Buggy python submission (verdict: Time Limit Exceeded):
N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

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


Fixed submission:
N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

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