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 |