時間制限:$2.0sec$ / メモリ制限:$256MB$
$N$頂点$M$辺の重み付き無向グラフが与えられます。
辺$e_i$は頂点$a_i$と頂点$b_i$を結んでいて、$a_i$と$b_i$の間を移動するのに$c_i$のコストがかかります。
頂点$1$から頂点$N$に移動するために必要な最小コストを求めてください。
但し、自己辺($a_i$ = $b_i$となる辺)は与えられず、辺の重複($i \neq j$ のときに$a_i = a_j,b_i = b_j$の両方が成り立つこと)もないことが保証されます。
さらに、テストケース1~5では、$2 ≦ N ≦ 100,1 ≦ M ≦ 200 $が
テストケース6~10では、$2 ≦ N ≦ 2000,1 ≦ M ≦ 4000 $が
テストケース11~15では、$c_i = 1$が追加制約として与えられます。
入力は以下の形式で標準入力から与えられる。
N M
a_1 b_1 c_1
a_2 b_2 c_2
......
a_M b_M c_M
頂点$1$から頂点$N$に移動するために必要な最小コストを出力してください。
但し、移動できない場合には$-1$を出力してください。
3 2
1 2 3
2 3 5
8
頂点$1$から頂点$2$に移動するのに$3$のコストがかかり、頂点$2$から頂点$3$に移動するのに$5$のコストがかかります。
4 1
1 3 33
-1
残念ながら頂点$1$から頂点$4$に移動することはできません。