import sys
input = sys.stdin.readline
INF = 10**9
def BF():
DP = [INF]*N
DP[0] = 0
for i in range(N):
for x,y,w in graph:
if DP[x] == INF:
continue
if DP[y] > DP[x]+w:
DP[y] = DP[x]+w
if i == N-1:
return False
return DP
N,M = map(int,input().split())
graph = []
for i in range(M):
x,y,w = map(int,input().split())
graph.append((x-1,y-1,w))
result = BF()
if result:
for i in range(1,N):
if result[i] == INF:
print(-1)
else:
print(result[i])
else:
print(-1)
전형적인 벨만포드 알고리즘 문제이다.
복습하는 겸 풀어보았다.