当前没有测试数据。

Ex - 使Q题目

得分：625分

问题描述

有一个简单无向图，有$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$
• $(A_i,B_i) \neq (A_j,B_j)$，其中$i \neq 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$。

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连接起来。

所以可以以总代价$4+5+3+2+1=15$的方式使Q。 以其他方式使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