백준 11657 타임머신

import sys
input = sys.stdin.readline

INF = int(1e9)
n, m = map(int, input().split())
g = []
for _ in range(m):
    a, b, c = map(int, input().split())
    g.append((a-1, b-1, c))

d = [INF] * n
# 시작노드를 0으로 초기화
d[0] = 0
go_back = 0
# 정점 수 만큼 반복
for i in range(n):
    # 간선마다 다 확인
    for j in range(m):
        now = g[j][0]
        next = g[j][1]
        cost = g[j][2]
        if d[now] != INF and d[now] + cost < d[next]:
            d[next] = d[now] + cost
            # 정점수-1까지만 돌면 최단경로 구하는데 만약
            # n-1까지(n번) 돌았으면 또 갱신됐기 때문에 이후 계속 돌면
            # 음의 무한대로 수렴한다 -> 음의 사이클 
            if i == n-1:
                go_back = -1
       
if go_back == -1:
    print(go_back)
else:
    for i in range(1, n):
        if d[i] == INF:
            print(-1)
        else:
            print(d[i])

음수 있을 때 : 벨만 포드
벨만 포드 정리 & 다익스트라로는 왜 안되는지도 생각