[ABC308Ex] Make Q

现在有一个由 $N$ 个点组成的 $M$ 条边的简单无向图。一开始所有的边都是白色的。点编号为 $1,2,3,\dots,N$，第 $i$ 条边连接点 $A_i$, $B_i$，并且将这条边染为黑色的代价为 $C_i$。你现在需要染色至少四条边，使得： 1、除了某条染为黑色的边以外，剩下所有黑色的边构成一个简单环 2、不在该简单环上的黑色的边连接了一个该简单环上的点和一个不在该简单环上的点 请判断能否染色成功，如果能，输出最小代价，如果不能，则输出 ``-1``。

[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 $ を出力せよ。

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

15

4 4
1 2 1
2 3 1
3 4 1
1 4 1

-1

6 15
2 6 48772
2 4 36426
1 6 94325
3 6 3497
2 3 60522
4 5 63982
4 6 4784
1 2 14575
5 6 68417
1 5 7775
3 4 33447
3 5 90629
1 4 47202
1 3 90081
2 5 79445

78154

### 制約 - $ 4\leq\ N\ \leq\ 300 $ - $ 4\leq\ M\ \leq\ \frac{N(N-1)}{2} $ - $ 1\ \leq\ A_i\ <\ B_i\ \leq\ N $ - $ i\ \neq\ j $ ならば $ (A_i,B_i)\ \neq\ (A_j,B_j) $ - $ 1\ \leq\ C_i\ \leq\ 10^5 $ - 入力は全て整数 ### Sample Explanation 1 辺 $ 2,3,4,5,6 $ を黒く塗ると、 - 辺 $ 2,4,5,6 $ が $ 1 $ つの単純サイクルをなす - 辺 $ 3 $ が頂点 $ 3 $（上記のサイクルに含まれる）と頂点 $ 1 $（上記のサイクルに含まれない）を結ぶ ため、総コスト $ 4+5+3+2+1=15 $ で Q を作ることができます。 他の方法で Q を作っても総コストは $ 15 $ 以上かかるため、答えは $ 15 $ です。