Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            for a, b, c in edges:
                V[b] = min(V[b], V[a] + c)

    bf(N)

    Vb = tuple(V)
    bf(1)

    if tuple(V) == Vb:
        print(max(-V[-1], 0))
    else:
        print(-1)

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)

def main():
    ii = lambda: int(input())
    mis = lambda: map(int, input().split())
    lmis = lambda: list(mis())

    N, M, P = mis()

    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = [(a, b, c) for a, b, c in edges if a in ok and b in ok]

    V = [float('inf')] * N
    V[0] = 0

    def bf_step():
        for a, b, c in edges:
            V[b] = min(V[b], V[a] + c)

    def bf():
        for _ in range(N):
            bf_step()

    bf()

    Vb = tuple(V)
    bf_step()

    if tuple(V) == Vb:
        print(max(-V[-1], 0))
    else:
        print(-1)

main()


Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = set()
reachableToN = set()

# dfs
reachableFrom0.add(0)
nodes = [0]
while nodes:
    node = nodes.pop()
    for i in to[node]:
        if i not in reachableFrom0:
            nodes.append(i)
            reachableFrom0.add(i)

#rdfs
reachableToN.add(N-1)
nodes = [N-1]
while nodes:
    node = nodes.pop()
    for i in ot[node]:
        if i not in reachableToN:
            nodes.append(i)
            reachableToN.add(i)


ok = reachableFrom0 & reachableToN

edges = [(a, b, c) for a, b, c in edges if a in ok and b in ok]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    reachableFrom0[0] = True
    nodes = [n]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if not reachableFrom0[i]:
                nodes.append(i)
                reachableFrom0[i] = True


def rdfs(n):
    reachableToN[n] = True
    nodes = [n]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if not reachableToN[i]:
                nodes.append(i)
                reachableToN[i] = True

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]

edges = [(a, b, c) for a, b, c in edges if ok[a] and ok[b]]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    if reachableFrom0[n]:
        return
    reachableFrom0[n] = True
    for i in to[n]:
        dfs(i)

def rdfs(n):
    if reachableToN[n]:
        return
    reachableToN[n] = True
    for i in ot[n]:
        rdfs(i)

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]

edges = [(a, b, c) for a, b, c in edges if ok[a] and ok[b]]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Runtime Error):
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    if reachableFrom0[n]:
        return
    reachableFrom0[n] = True
    for i in to[n]:
        dfs(i)

def rdfs(n):
    if reachableToN[n]:
        return
    reachableToN[n] = True
    for i in ot[n]:
        rdfs(i)

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]

edges = [(a, b, c) for a, b, c in edges if ok[a] and ok[b]]

V = [float('inf')] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Runtime Error):
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    if reachableFrom0[n]:
        return
    reachableFrom0[n] = True
    for i in to[n]:
        dfs(i)

def rdfs(n):
    if reachableToN[n]:
        return
    reachableToN[n] = True
    for i in ot[n]:
        rdfs(i)

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]

edges = [(a, b, c) for a, b, c in edges if ok[a] and ok[b]]

V = [10**10] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        if ok[a] and ok[b]:
            V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Runtime Error):
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    if reachableFrom0[n]:
        return
    reachableFrom0[n] = True
    for i in to[n]:
        dfs(i)

def rdfs(n):
    if reachableToN[n]:
        return
    reachableToN[n] = True
    for i in ot[n]:
        rdfs(i)

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]


V = [10**10] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        if ok[a] and ok[b]:
            V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf_step()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()

Buggy python submission (verdict: Runtime Error):
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

N, M, P = mis()

to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for i in range(M):
    a,b,c = mis()
    a -= 1
    b -= 1
    c = -(c-P)
    #
    to[a].append(b)
    ot[b].append(a)
    edges.append((a,b,c))

reachableFrom0 = [False] * N
reachableToN = [False] * N

def dfs(n):
    if reachableFrom0[n]:
        return
    reachableFrom0[n] = True
    for i in to[n]:
        dfs(i)

def rdfs(n):
    if reachableToN[n]:
        return
    reachableToN[n] = True
    for i in ot[n]:
        rdfs(i)

dfs(0)
rdfs(N-1)

ok = [a and b for a, b in zip(reachableFrom0, reachableToN)]


V = [10**10] * N
V[0] = 0

def bf_step():
    for a, b, c in edges:
        if ok[a] and ok[b]:
            V[b] = min(V[b], V[a] + c)

def bf():
    for _ in range(N):
        bf_step()

bf()

Vb = tuple(V)
bf()

if tuple(V) == Vb:
    print(max(-V[-1], 0))
else:
    print(-1)




Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())

def main():
    N, M, P = mis()
    
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for i in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        c = -(c-P)
        #
        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFrom0 = set()
    reachableToN = set()

    # dfs
    reachableFrom0.add(0)
    nodes = [0]
    while nodes:
        node = nodes.pop()
        for i in to[node]:
            if i not in reachableFrom0:
                nodes.append(i)
                reachableFrom0.add(i)

    #rdfs
    reachableToN.add(N-1)
    nodes = [N-1]
    while nodes:
        node = nodes.pop()
        for i in ot[node]:
            if i not in reachableToN:
                nodes.append(i)
                reachableToN.add(i)


    ok = reachableFrom0 & reachableToN

    edges = tuple((a, b, c) for a, b, c in edges if a in ok and b in ok)

    V = [float('inf')] * N
    V[0] = 0

    def bf(n):
        for _ in range(n):
            upd = False
            for a, b, c in edges:
                if V[b] > V[a] + c:
                    V[b] = V[a] + c
                    upd = True
            if not upd:
                return False
        return True

    bf(N)

    if not bf(1):
        print(max(-V[-1], 0))
    else:
        print(-1)

main()