A16528 | $Secret Message$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

在土耳其漫长的旅行中，你见过许多不同的马赛克，但你从未遇到过像这样的马赛克！ 你目前看到的这幅马赛克可以看作是一张包含 $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$。

输入 #1

输出 #1

C++ 编辑器

输入

输出