출력

첫째 줄에는 2번 도시까지 가는 가장 빠른 시간, ..., N-1번째 줄에는 N번 도시까지 가는 가장 빠른 시간을 출력한다. 어떤 도시로 가는 (1)가장 빠른 시간이(->경로가) 없는 경우에는 -1을 출력한다.

만약, 1번 도시에서 출발해 시간을 무한히 오래 전으로 되돌리는 방법이 존재해 (2)1번 도시에서 나머지 도시로 가는 가장 빠른 시간이 존재하지 않는 경우에는(->어떤 도시로 가는 경로는 있으나 가장 빠른 시간이 없는 경우가 있다면) -1을 ((3)한 번만) 출력한다.

(2) 의 경우, '1번 도시가 가중치 합이 음인 사이클에 포함되어 다른 모든 도시로의 가장 빠른 시간이 존재 하지 않는 경우'로 이해할 수 있을 것 같고,

(1) 의 경우, '해당 도시로의 경로는 존재하나 가장 빠른 시간은 없는 경우'와 혼동할 여지가 있어보여 위와 같이 수정을 건의합니다.

아울러 데이터 추가 요청합니다

//Input
4 5
1 4 3
4 2 4
2 3 -4
3 4 -2
4 3 3

/*
Answer
-1

Output(AC)
-13991
-1
-13995
*/