타임머신

시간 제한1초메모리 제한256 MB

요약

출발 도시 1에서 각 도시까지 음수 시간이 있는 버스 노선으로 가장 빠른 시각을 구하고 도달 가능한 음수 사이클이 있으면 -1을 출력합니다.

난이도: 보통10점 중 4점
유형: 최단 경로, 그래프
정답자: 아직 제출이 없습니다

문제

도시가 $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$ 이면 아무것도 출력하지 않는다.

예제3

예제 1
입력
```
3 4
1 2 4
1 3 3
2 3 -1
3 1 -2
```
예상 출력
```
4
3
```
예제 2
입력
```
3 4
1 2 4
1 3 3
2 3 -4
3 1 -2
```
예상 출력
```
-1
```
예제 3
입력
```
3 2
1 2 4
1 2 3
```
예상 출력
```
3
-1
```