벨만-포드 - 11657번: 타임머신

• 음수 가중치의 간선이 있을 때의 최단경로 문제 -> 벨만-포드 알고리즘
• 사이클 없는 최단경로는 최대 V-1개의 간선만 포함함
• 완화 연산: if dist[v] > dist[u] + w 거리가 더 짧아지면 갱신!
• V-1번 완화해서 모든 최단경로 구하기
• V-1번 후에도 최단경로가 또 갱신되면 시작점에서 도달 가능한 음수 사이클이 존재함을 의미함!

import sys

input = sys.stdin.readline

N, M = map(int, input().split())


bus_list = []

for i in range(M):
    a, b, c = map(int, input().split())

    bus_list.append((a, b, c))


# 음수 가중치의 간선이 존재하므로 벨만-포드 알고리즘 사용
def bellman_ford(start):

    dist = [float("inf")] * (N + 1)
    dist[start] = 0

    # V - 1 번 돌리기
    for _ in range(N - 1):
        updated = False

        for u, v, w in bus_list:

            if dist[u] != float("inf") and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                updated = True

        if not updated:
            break

    # 전체 경로를 1번 다 돌고도, 추가 1라운드에서 최단거리 갱신이 또 일어난다면, 음수 사이클이 존재함을 의미
    negative_cycle = False
    for u, v, w in bus_list:

        if dist[u] != float("inf") and dist[v] > dist[u] + w:
            negative_cycle = True
            break

    return dist, negative_cycle


# 1번 도시에서 출발
dist, negative_cycle = bellman_ford(1)


# 음수 사이클이 존재하여 시간을 무한히 오래 전으로 되돌릴 수 있다면 -> 최단경로 보장이 안됨, -1 출력
if negative_cycle:
    print(-1)
else:
    for i in range(2, N + 1):
        # 해당 도시로 가는 경로가 없다면 -1 출력
        if dist[i] == float("inf"):
            print(-1)
        else:
            print(dist[i])