은하계에는 \(N\)개의 정거장이 있고, 정거장 사이를 잇는 \(M\)개의 단방향 웜홀이 있다. \(i\)번째 웜홀을 타면 정거장 \(a_i\)에서 \(b_i\)로 이동하며, 이때 시간이 \(c_i\)만큼 흐른다. \(c_i\)는 음수일 수도 있는데, 이는 과거로 시간을 되돌린다는 뜻이다.

탐험가는 1번 정거장에서 출발한다. 각 정거장 \(v\)(\(2 \le v \le N\))에 대해, 1번에서 \(v\)로 가는 동안 흐르는 시간의 최솟값을 구하여라.

단, 어떤 정거장을 지나는 경로를 무한히 반복하여 시간을 무제한으로 거꾸로 돌릴 수 있다면 (즉 1번에서 도달 가능한 음수 사이클이 존재하면), 답을 정의할 수 없으므로 \(-1\) 한 줄만 출력한다. 1번에서 도달할 수 없는 정거장 \(v\)에 대해서는 \(\texttt{INF}\)를 출력한다.

\(2 \le N \le 500\)

\(1 \le M \le 6{,}000\)

\(-10{,}000 \le c_i \le 10{,}000\)

첫째 줄에 정거장의 수 \(N\)과 웜홀의 수 \(M\)이 주어진다.

다음 \(M\)개의 줄에 각각 세 정수 \(a_i\), \(b_i\), \(c_i\) (\(1 \le a_i, b_i \le N\), \(-10{,}000 \le c_i \le 10{,}000\))가 주어진다.

1번에서 도달 가능한 음수 사이클이 있으면 \(-1\) 한 줄만 출력한다.

그렇지 않으면 \(v = 2, 3, \dots, N\) 순서대로, 1번에서 \(v\)로 가는 최소 시간을 한 줄에 하나씩 출력한다. 도달할 수 없으면 \(\texttt{INF}\)를 출력한다.

riseoj 작성

출처 Original