题目描述

有一个简单无向图，有 $N$ 个顶点和 $M$ 条边。初始时，所有边都被涂成白色。顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，将其涂成黑色的花费是 $C_i$。

"构造一个 Q" 的意思是涂四条或更多的边，使得：

• 涂成黑色的除了一条边以外的边构成一个简单环，且
• 涂成黑色的不构成环的边连接一个环上的顶点和另一个不在环上的顶点。

确定是否可以构造一个 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，请打印所需的最小总花费；否则，打印 $-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$ 构成一个简单环，且
• 边 $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