Shared code

import sys

input = sys.stdin.readline


def bellman_ford(n, edges, start):
    dist = [float("inf")] * n

    dist[start] = 0

    for _ in range(n):
        for u, v, d in edges:
            if dist[u] + d < dist[v]:
                dist[v] = dist[u] + d

    last = dist[n - 1]
    for _ in range(n):  # do n more times, to check if last guy change.
        for u, v, d in edges:
            if dist[u] + d < dist[v]:  # reduce both by large amount
                dist[v] = dist[u] + d - 10**10
                dist[u] -= 10**10

    if last == dist[n - 1]:
        return -last
    else:
        return -1


# bellman ford with negated edges
def main():
    n, m = list(map(int, input().split()))
    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((u - 1, v - 1, -w))
    ans = bellman_ford(n, edges, 0)
    print(ans)


main()