AT_abc308_h [ABC308Ex] Make Q

[problemUrl]: https://atcoder.jp/contests/abc308/tasks/abc308_h $ N $ 頂点 $ M $ 辺の単純無向グラフがあり、最初全ての辺は白く塗られています。 頂点には $ 1 $ から $ N $ までの番号が、辺には $ 1 $ から $ M $ までの番号がそれぞれ付けられています。 辺 $ i $ は頂点 $ A_i $ と頂点 $ B_i $ を結んでおり、この辺を黒く塗るのにかかるコストは $ C_i $ です。 $ 4 $ 本以上の辺を黒く塗ることで以下の条件を全て満たすようにすることを「Q を作る」といいます。 - 黒く塗られた辺のうちある $ 1 $ 本以外は、$ 1 $ つの単純サイクルをなす。 - 黒く塗られた辺のうち上記のサイクルに含まれない $ 1 $ 本は、そのサイクルに含まれる頂点と含まれない頂点を結ぶ。 Q を作ることが可能かどうか判定し、可能ならば Q を作るのに必要な最小の総コストを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

Q を作ることが可能ならば Q を作るのに必要な最小の総コストを、不可能ならば $ -1 $ を出力せよ。

### 制約 - $ 4\leq\ N\ \leq\ 300 $ - $ 4\leq\ M\ \leq\ \frac{N(N-1)}{2} $ - $ 1\ \leq\ A_i\