negative_cycle.py

import sys


def negative_cycle(adj, cost):
    #write your code here
    dist = [n+1] * n
    prev = [None] * n
    dist[0] = 0
    for _ in range(n-1):
        for u, edges in enumerate(adj):
            for i, v in enumerate(edges):
                if dist[v]>dist[u]+cost[u][i]:
                    dist[v]=dist[u]+cost[u][i]
                    prev[v]=u
    for u, edges in enumerate(adj):
        for i, v in enumerate(edges):
            if dist[v]>dist[u]+cost[u][i]:
                return 1
    return 0


if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3]))
    data = data[3 * m:]
    adj = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for ((a, b), w) in edges:
        adj[a - 1].append(b - 1)
        cost[a - 1].append(w)
    print(negative_cycle(adj, cost))