CF2174D Secret Message

在土耳其漫长的旅行中，你见过许多不同的马赛克，但你从未遇到过像这样的马赛克！ 你目前看到的这幅马赛克可以看作是一张包含 $n$ 个顶点和 $m$ 条带权边的无向图，其中第 $i$ 条边的权值为 $w_i$。你对它印象深刻，决定寻找其中隐藏的秘密信息。你考虑了很多种可能性，目前你假设这个秘密与从中选出 $n-1$ 条边的权值和最小且选出的这些边不形成一棵树有关。 你首先想计算出这个值，至于它的意义，你打算回家后再研究。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$2 \le n \le 2 \times 10^5$，$n-1 \le m \le 2 \times 10^5$），表示无向图的顶点数和边数。 接下来的 $m$ 行中，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i \ne v_i \le n$，$1 \le w_i \le 10^9$），表示第 $i$ 条无向边连接 $u_i$ 和 $v_i$，权值为 $w_i$。 保证图中不存在自环或重边。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，$m$ 的总和也不超过 $2 \times 10^5$。

对每个测试用例，输出一个整数：表示选取 $n-1$ 条边且这些边不组成树的边权和的最小值。如果不存在这样的方案，则输出 $-1$。

在第一个测试用例中，可以选择第 2、3 和第 6 条边，其边权和为 $4 + 1 + 5 = 10$。可以验证，这些边不构成一棵树。 在第二个测试用例中，所有可能的 $3$ 条边子集都会形成一棵树，因此不存在满足条件的方案。 由 ChatGPT 5 翻译