交通混雑度
n 個の都市が m 本の道路によってつながっています。各道路は輸送ルートであり、混雑度を示す値 を持っています。これはその道路の渋滞度合いを表すものです。
ここでの目的は、都市 1 から各都市
i までの「経路上の混雑度」をできるだけ小さくすることです。経路上の混雑度は、その経路に含まれる道路のうち、最大の混雑度 () を持つ道路の値として定義します。入力
最初の行には、空白区切りで 2 つの整数
n と m () が与えられ、これは都市の数と道路の数を表します。続く
m 行の各行には、空白区切りで 3 つの整数 、 () が与えられ、これは都市 と を結ぶ道路の混雑度 を示します。出力
都市 1 から都市
i+1 に至る際に考えられる最小の経路上の混雑度を、n-1 個の整数として 1 行に出力してください。ここで、i 番目の整数が都市 1 から都市 i+1 までの最小の経路上の混雑度になります。例
Input | Output |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB