타임머신

도시가 $N$개 있다. 한 도시에서 출발해 다른 도시에 도착하는 버스 노선은 $M$개다. 각 노선은 세 정수 $A$, $B$, $C$로 나타낸다. $A$는 출발 도시, $B$는 도착 도시, $C$는 그 버스를 타고 이동하는 데 걸리는 시간이다.

$C$가 양수가 아닌 경우도 있다. $C = 0$이면 순간 이동이고, $C < 0$이면 타임머신을 타고 시간을 되돌아간다.

1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 $N$ ($1 \le N \le 500$)과 버스 노선의 개수 $M$ ($1 \le M \le 6000$)이 주어진다.

둘째 줄부터 $M$개 줄에 걸쳐 노선 정보 $A$, $B$, $C$ ($1 \le A, B \le N$, $-10000 \le C \le 10000$)가 주어진다. 같은 두 도시를 잇는 노선이 여러 개일 수도 있고, $A = B$인 노선이 있을 수도 있다.

1번 도시에서 출발해 어떤 도시로 가는 도중에 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

그렇지 않다면 $N - 1$개 줄에 걸쳐 1번 도시에서 2번 도시, 3번 도시, ..., $N$번 도시로 가는 가장 빠른 시간을 순서대로 한 줄에 하나씩 출력한다. 그 도시로 가는 경로가 없다면 그 줄에는 -1을 출력한다. $N = 1$이면 아무것도 출력하지 않는다.