\(N\) 頂点 \(M\) 辺の単純連結な無向グラフがあり、最初全ての辺は白く塗られています。頂点には \(1\) から \(N\) までの番号が、辺には \(1\) から \(M\) までの番号がそれぞれ付けられています。辺 \(i~(1 \le i \le M)\) は頂点 \(u_i\) と頂点 \(v_i\) を結んでおり、この辺を黒く塗るのにかかるコストは \(w_i\) です。
\(6\) 本以上の辺を黒く塗ることで以下の条件を全て満たすようにすることを「\(8\) を作る」といいます。
\(8\) を作ることが可能かどうか判定し、可能ならば \(8\) を作るのに必要な総コストの最小値を求めてください。
入力は以下の形式で標準入力から与えられます。
| \(N~M\) | |
| \(u_1~u_1~w_1\) | |
| \(u_2~u_2~w_2\) | |
| \(\vdots\) | |
| \(u_M~v_M~w_M\) |
入力は以下の制約をすべて満たします。
\(8\) を作ることが可能ならば、\(8\) を作るために必要な総コストの最小値を出力してください。不可能ならば -1 を出力してください。
以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。
5 81 2 11 3 11 4 11 5 12 3 23 4 34 5 42 5 5
10
4 51 2 11 3 11 4 12 3 23 4 3
-1
Sample 1：\(A=\{1, 2, 3\}, B=\{1, 4, 5\}\) とすることで条件を満たすことができます。
Sample 2：条件を満たす 2 つのサイクルは存在しません．
| Sample 1 | Sample 2 |