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