Problem
방향 가중치 그래프가 제공됩니다. 1 - k BFS 알고리즘을 사용하여 상단 1에서 다른 모든 항목까지의 거리를 찾아야 합니다.
입력
첫 번째 줄에는 각각 그래프의 꼭지점과 가장자리의 수인 2개의 정수 n 및 m이 포함됩니다. 다음 m 줄에는 각 a 및 b(가장자리가 연결되는 정점 및 c)가 있는 3개의 숫자가 포함되어 있습니다. 이 가장자리의 가중치(a, b, c >= 0).
출력
공백으로 구분된 n-1 번호를 출력해야 합니다. 1에서 가능한 경로가 없는 경우 상단 1에서 다른 모든 항목까지의 거리입니다. 를 i 정점으로 변환한 다음 Impossible을 출력해야 합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
<예비>
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
<예비>
1 4 3 6 4 불가능 불가능 불가능
|