AT_pakencamp_2021_day2_l ジグザグ道

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day2/tasks/pakencamp_2021_day2_l $ 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_3\ \ C_2\ \ \cdots $ である。つまり、次の条件のいずれかを満たす。 - 任意の整数 $ i\ \,\ (1\ \leq\ i\ \leq\ k\ -\ 1) $ について、 $ i $ が奇数ならば $ C_i\ \ C_{i+1} $ である。 - 任意の整数 $ i\ \,\ (1\ \leq\ i\ \leq\ k\ -\ 1) $ について、 $ i $ が奇数ならば $ C_i\ >\ C_{i+1} $ であり、 $ i $ が偶数ならば $ C_i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ W_1 $ $ U_2 $ $ V_2 $ $ W_2 $ $ \vdots $ $ U_M $ $ V_M $ $ W_M $

*ジグザグ道*が存在する場合は、通る辺の重みの総和の最小値を $ 1 $ 行に出力せよ。*ジグザグ道*が存在しない場合は `-1` を $ 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\