1257 - ダイクストラ大好き厨とコーナーテストケース

問題

ダイクストラ大好き厨であるあなたは、あるコーナーテストケースを発見してしまった。

それは自己辺・多重辺無し、無向グラフの場合でも以下の図のような状況の時に起こる。

ノード数を V 、エッジ数を E とした時、上の図の中央のノードにおいて、優先度付きキューに E/4 個の要素が入った状態で E/4 個のエッジを見てしまう。これにより O(E^2) となってしまうことにあなたは気が付いた。

これを見つけたあなたは、部員からのダイクストラのイメージが下がってしまうことを懸念し、このコーナーケースを回避することにした。

コーナーケースを回避しつつ、地点 1 から地点 V までの最短距離を求めるプログラムを書いて欲しい。

入力

V E
a1 b1 c1
・
・
・
aE bE cE

1 行目にノード数 V 、エッジ数 E が与えられる。

続く E 行に、ノード a , b とエッジのコスト c が与えられる。

出力

ノード 1 からノード V までの最短距離を出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• 2 ≦ V ≦ 10⁵
• 1 ≦ E ≦ min(2 * 10⁵,V(V-1)/2)
• 1 ≦ a,b ≦ V
• 1 ≦ c ≦ 5 * 10⁴

※答えが32bit整数型の範囲を超える可能性がありますが、ここでは気にしなくていいです。

---

入出力例

入力例

7 8
1 2 1
1 3 1
2 4 2
3 4 1
4 5 10
4 6 10
5 7 10
6 7 10

出力例

22

解説

上の図の E=8 のケースである。

作問者より

大学のLT(Lightning Talk)で作ったので、おすそ分けです。

ソースコードも公開してるので、ぜひダイクストラ法をブラッシュアップしてください（解いてない人でも見れたっけ？）。

問題文で曖昧なところがあったり、明らかに正しいのにWAが出る場合はtwitterの@tonphy_1322007までお願いします。