// problem #83

타임머신 (벨만-포드)

N개 도시와 M개의 이동 수단이 있고 이동 시간은 음수일 수 있다. 1번에서 각 도시로 가는 최소 시간을 구하시오. 음수 사이클로 시간을 무한히 되돌릴 수 있으면 -1을 출력한다.

입력

첫 줄 N, M. 이후 M개 줄에 a b c (a→b, 시간 c, 음수 가능).

출력

음수 사이클이 있으면 -1. 아니면 2번부터 N번까지 최소 시간을 한 줄씩(도달 불가 INF).

제한

• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 6,000
• |c| ≤ 10,000

예제

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

4
3

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

-1