第2最短経路
あなたには
n 個の都市と、それらを結ぶ m 本の双方向道路が与えられています。各道路には、それぞれ長さ が割り当てられています。旅行好きの冒険家である Emil は、これらの道路を使って都市 1 から都市 n へ向かおうとしています。ただし彼の計画にはひとつ工夫があり、最短経路よりも厳密に長い経路の中で、最も短い道のりを選ぼうとしているのです。つまり、あなたの役割は、都市
1 から都市 n まで移動する「第2最短経路」の長さを求めることです。入力
入力の最初の行には、都市の数を表す整数
n と道路の数を表す整数 m が与えられます。続く m 行には、, , の3つの整数が書かれており、それぞれ都市 と都市 を結ぶ長さ の双方向道路が存在することを意味します。出力
都市
1 から都市 n までの「第2最短経路」の長さを表す整数を1つ出力してください。例
入力 | 出力 |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB