Problem
여러 에지와 루프를 가질 수 있는 유방향 그래프가 주어집니다. 각 모서리에는 정수(음수일 수 있음)로 표시되는 가중치가 있습니다. 음수 가중치 주기가 없음을 보장합니다.
1번 정점에서 다른 모든 정점까지의 최단 경로 길이를 계산해야 합니다.
입력
프로그램은 먼저 숫자 N(1 <= N <= 100)을 받습니다. 그래프 정점의 수와 수 M(0 <= M <= 10000) – 갈비뼈의 수. 다음 줄에는 가장자리를 설명하는 M개의 트리플 숫자가 포함되어 있습니다: 가장자리의 시작, 가장자리의 끝 및 가중치(가중치 –는 -100에서 100까지의 정수임).
출력
프로그램은 N개의 숫자를 출력해야 합니다. 정점 번호 1에서 그래프의 모든 정점까지의 거리. 해당 정점에 대한 경로가 없으면 경로의 길이 대신 숫자 30000을 인쇄하십시오.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |