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 翻译