在土耳其的长途旅行中,您见过许多不同的马赛克,但您从未遇到过这样的马赛克!
您看到的马赛克是一个具有 $$$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$$$。
示例
输入复制
44 61 2 71 3 41 4 12 3 92 4 63 4 54 41 2 52 3 53 4 51 4 84 41 4 11 3 42 4 23 4 34 42 3 71 2 52 4 94 3 12
输出复制
10-1828
注意
在第一个测试用例中,您可以选择第二、第三和第六条边,其权重总和为$$$4 + 1 + 5 = 10$$$。可以验证这组边并没有形成一棵树。
在第二个测试用例中,$$$3$$$ 边的所有可能子集将形成一棵树。因此,没有解决办法。