問題文

$N$ 頂点 $M$ 辺の単純無向グラフがあり、最初全ての辺は白く塗られています。 頂点には $1$ から $N$ までの番号が、辺には $1$ から $M$ までの番号がそれぞれ付けられています。 辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでおり、この辺を黒く塗るのにかかるコストは $C_i$ です。

$4$ 本以上の辺を黒く塗ることで以下の条件を全て満たすようにすることを「Q を作る」といいます。

• 黒く塗られた辺のうちある $1$ 本以外は、$1$ つの単純サイクルをなす。
• 黒く塗られた辺のうち上記のサイクルに含まれない $1$ 本は、そのサイクルに含まれる頂点と含まれない頂点を結ぶ。

Q を作ることが可能かどうか判定し、可能ならば Q を作るのに必要な最小の総コストを求めてください。

制約

• $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$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\\vdots$ $A_M$ $B_M$ $C_M$

出力

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

入力例 1

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

出力例 1

15

辺 $2,3,4,5,6$ を黒く塗ると、

• 辺 $2,4,5,6$ が $1$ つの単純サイクルをなす
• 辺 $3$ が頂点 $3$（上記のサイクルに含まれる）と頂点 $1$（上記のサイクルに含まれない）を結ぶ

ため、総コスト $4+5+3+2+1=15$ で Q を作ることができます。 他の方法で Q を作っても総コストは $15$ 以上かかるため、答えは $15$ です。

入力例 2

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

出力例 2

-1

入力例 3

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

出力例 3

78154