← 返回题目列表

Codeforces · 2174/D

D. 秘密消息

中文机器翻译题面 查看原题

在土耳其的长途旅行中,您见过许多不同的马赛克,但您从未遇到过这样的马赛克!

您看到的马赛克是一个具有 $$$n$$$ 个顶点和 $$$m$$$ 边、权重 $$$w_i$$$ 的图。它给你留下了深刻的印象,你决定寻找其中包含的秘密信息。您已经考虑了许多不同的选项,您当前的假设是秘密是一组 $$$n - 1$$$ 边的权重之和,使得总和最小并且边不形成树。

首先,您想要找出这个值,以及您打算在回家的路上弄清楚它意味着什么。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 2 \cdot 10^5$$$) - 分别是图中的顶点数和边数。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i \ne v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) - 的描述第 $$$i$$$ 条边。

保证图不包含自环或多边。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 不形成树的一组 $$$n - 1$$$ 边的最小权重总和(如果存在这样的一组)。否则,打印$$$-1$$$。

示例

输入
复制

4
4 6
1 2 7
1 3 4
1 4 1
2 3 9
2 4 6
3 4 5
4 4
1 2 5
2 3 5
3 4 5
1 4 8
4 4
1 4 1
1 3 4
2 4 2
3 4 3
4 4
2 3 7
1 2 5
2 4 9
4 3 12

输出
复制

10
-1
8
28

注意

在第一个测试用例中,您可以选择第二、第三和第六条边,其权重总和为$$$4 + 1 + 5 = 10$$$。可以验证这组边并没有形成一棵树。

在第二个测试用例中,$$$3$$$ 边的所有可能子集将形成一棵树。因此,没有解决办法。