[python] 백준 - 11657 (타임 머신)

import sys
input = sys.stdin.readline

def bellman_ford(ver, edges, start):
    distance = [float('inf')] * (ver + 1)
    distance[start] = 0

    for i in range(ver - 1):
        for u, v, w in edges:
            if distance[u] != float('inf') and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    for u, v, w in edges:
        if distance[u] != float('inf') and distance[u] + w < distance[v]:
            return -1

    for i in range(2, len(distance)):
        if distance[i] == float('inf'):
            distance[i] = -1
    return distance

n, m = map(int, input().split())

edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

start = 1
result = bellman_ford(n, edges, start)

if result != -1:
    print('\n'.join(map(str, result[2:])))
else:
    print(result)