AT_abc308_h.[ABC308Ex] Make Q

有一个包含 $N$ 个顶点、$M$ 条边的简单无向图，最开始所有的边都是白色的。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，将这条边涂成黑色需要花费 $C_i$ 的代价。

通过将至少 $4$ 条边涂成黑色，并满足以下所有条件的操作，称为“构造 Q”：

• 除了一条黑色边以外，其余所有黑色边恰好构成一个简单环。
• 那条不在上述环中的黑色边，连接了属于该环的顶点和不属于该环的顶点。

请判断是否可以构造 Q，如果可以，请求出构造 Q 所需的最小总代价；如果不可以，输出 $-1$。

输入按以下格式从标准输入读入：

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

如果可以构造 Q，则输出构造 Q 所需的最小总代价；如果不可以，输出 $-1$。

限制条件

• $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$
• 所有输入均为整数

样例解释 1

将第 $2,3,4,5,6$ 条边涂成黑色时：

• 边 $2,4,5,6$ 恰好构成一个简单环；
• 边 $3$ 连接了顶点 $3$（属于上述环）和顶点 $1$（不属于上述环）；

因此，总代价为 $4+5+3+2+1=15$，可以构造 Q。用其他方法构造 Q 的总代价也不会小于 $15$，所以答案为 $15$。

由 ChatGPT 4.1 翻译