10101 타임머신 Gold IV

문제

N개의 도시와 M개의 버스(방향 있음)가 있다. 각 버스는 시간이 걸리며, 음수일 수도 있다. 1번 도시에서 나머지 도시까지의 최단 시간을 구하시오.

음수 사이클이 있으면 -1을 출력한다.

입력

첫째 줄에 N (1 ≤ N ≤ 500)과 M (1 ≤ M ≤ 6,000)이 주어진다. 다음 M줄에 A, B, C가 주어진다. (A → B, 시간 C, -10,000 ≤ C ≤ 10,000)

출력

2번~N번 도시까지 최단 시간을 한 줄에 하나씩 출력한다. 도달 불가면 -1, 음수 사이클이면 첫 줄에 -1만 출력한다.

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

4
3