构造 Q

题目描述

有一个 $N$ 个顶点、$M$ 条边的简单无向图。边最初全部为白色。

顶点编号为 $1$ 到 $N$,边编号为 $1$ 到 $M$。边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$,将它涂成黑色需要花费 $C_i$。

「构造 Q」是指涂黑四条或更多条边,使得:

• 涂黑的边中除一条外,其余边构成一个简单环;
• 那条不构成环的涂黑边连接环上的一个顶点和环外的一个顶点。

判断能否构造 Q。如果能,求出构造 Q 所需的最小总花费。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

如果能构造 Q,输出所需的最小总花费;否则输出 $-1$。

样例

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

15

通过涂黑边 $2,3,4,5,6$:

• 边 $2,4,5,6$ 构成一个简单环;
• 边 $3$ 连接顶点 $3$(在环上)和顶点 $1$(不在环上),

因此可以构造 Q,总花费为 $4+5+3+2+1=15$。

用其他方式构造 Q 的花费都大于或等于 $15$,所以答案是 $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 \le N \le 300$
• $4 \le M \le \frac{N(N-1)}{2}$
• $1 \le A_i \lt B_i \le N$
• 当 $i \neq j$ 时,$(A_i,B_i) \neq (A_j,B_j)$
• $1 \le C_i \le 10^5$
• 输入中的所有值均为整数