Find The Shortest Path 2

与えられた地図には、n 個の都市と、それらの都市を結ぶ m 本の双方向道路があります。各道路には非負整数の長さ が設定されています。あなたの課題は、都市 1 から都市 n へ至る最短経路の長さを求めることです。

入力

最初の行には、空白で区切られた 2 つの整数 n と m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000) が与えられ、これは都市の数と道路の本数を示します。

続く m 行には、それぞれ空白で区切られた 3 つの整数 、、 が記載されており、これは都市 と を結ぶ道路の長さ を表します (1 ≤ ui, vi ≤ n , 1 ≤ w_i ≤ 10^9)。

出力

都市 1 から都市 n までの最短経路の長さを表す整数を 1 つ出力してください。

例