問題文

N 頂点 M 辺の単純連結重み付き無向グラフが与えられます。頂点には 1 から N までの番号が、辺には 1 から M までの番号が振られています。辺 i は頂点 U_i と頂点 V_i を結び、重みは W_i です。辺の重みは全て互いに異なることが保証されます。

頂点 1 から頂点 N への、頂点の重複を許した道を考えます。通った辺の重みを順に並べた数列を C = (C_1, C_2, \ldots, C_k) として、次の条件を満たす道をジグザグ道と定義します。

• C_1 < C_2 > C_3 < \cdots または C_1 > C_2 < C_3 > \cdots である。つまり、次の条件のいずれかを満たす。
  • 任意の整数 i \, (1 \leq i \leq k - 1) について、 i が奇数ならば C_i < C_{i+1} であり、 i が偶数ならば C_i > C_{i+1} である。
  • 任意の整数 i \, (1 \leq i \leq k - 1) について、 i が奇数ならば C_i > C_{i+1} であり、 i が偶数ならば C_i < C_{i+1} である。

ジグザグ道は存在するでしょうか？存在するならば、通る辺の重みの総和の最小値も求めてください。

制約

• 2 \leq N \leq 10^5
• N - 1 \leq M \leq \min \left( \cfrac{N(N-1)}{2}, 10^5 \right)
• 1 \leq U_i < V_i \leq N
• 1 \leq W_i \leq 10^9
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• W_i \neq W_j \, (i \neq j)
• 入力で与えられるグラフは単純かつ連結
• 入力は全て整数

入力例 1

5 5
1 4 4
3 5 2
2 3 6
2 5 1
3 4 3

出力例 1

14

辺 1, 5, 3, 4 の順に通ると C = (4, 3, 6, 1) となり、ジグザグ道の条件を満たします。このとき重みの総和は 14 です。

辺 1, 5, 2 の順に通る道は C = (4, 3, 2) となりジグザグ道ではありません。

入力例 2

4 3
1 2 4
2 3 6
3 4 8

出力例 2

-1

入力例 3

7 12
2 5 657831697
5 6 925940778
1 2 749029915
2 4 237755672
3 6 60634766
6 7 65418621
1 4 194639839
4 7 411656898
3 7 367905753
3 4 241675120
1 6 858592389
2 6 571202751

出力例 3

562368346

原案: primenumber_zz