白駿11657号:タイムマシン

import sys
INF = float('inf')

N, M = map(int, sys.stdin.readline().split())

graph = {}  # 전체 graph는 dictionary임
for i in range(N):
    graph[i+1] = []  # 각 지점마다 각자의 array를 가지고 있음
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append([B, C])  # index 0이 지점, index 1이 비용인 array를 넣어줌

dist = [INF]*(N+1)


def bellman_ford(start):
    dist[start] = 0
    for i in range(N):
        for a in range(1, N+1):
            for b, c in graph[a]:
                if dist[b] > dist[a] + c:
                    dist[b] = dist[a] + c
                    if i == N-1:
                        return True
    return False


negativeCycle = bellman_ford(1)
if negativeCycle:
    print("-1")
else:
    for i in range(2, N+1):
        if dist[i] == INF:
            print("-1")
        else:
            print(dist[i])

dist = [INF]*(N+1)
dist[start] = 0

for i in range(N-1):  # 한번에 특정지어버리는 다익스트라와 다르게 N-1번 반복
    # 밑의 2중 for문의 최대 반복 횟수가 간선의 개수와 같으므로 시간복잡도 O(E)
    for a in range(1, N+1):  
        for b, c in graph[a]:  # (각 지점에서 연결된 간선의 개수만큼 반복)
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c

for i in range(N):  # N-1 -> N
    for a in range(1, N+1):
        for b, c in graph[a]:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                if i == N-1:  # N번째에 갱신되면 순환이 존재하는 것으로 판단
                    return True
return False   # 그렇지 않으면 존재 안하는 것으로 판단