CF2174D.Secret Message

During long excursions in Turkey, you have seen many different mosaics, but you have never encountered one like this!

The mosaic you see is a graph with $n$ vertices and $m$ edges of weight $w_i$. You are so impressed by it that you decided to search for a secret message contained within it. You have considered many different options, and your current hypothesis is that the secret is the sum of the weights of a set of $n - 1$ edges such that the sum is minimal and the edges do not form a tree.

First, you want to find out this value, and what it means you plan to figure out on your way back home.

在土耳其漫长而精彩的旅行中，你见过许多不同风格的镶嵌画，但从未见过这样一幅！

你眼前的这幅镶嵌画是一个包含 $n$ 个顶点和 $m$ 条边的图，其中第 $i$ 条边的权重为 $w_i$。你被它深深震撼，于是决定探寻其中隐藏的秘密信息。你考虑过多种可能性，目前的假设是：该秘密信息等于某组 $n - 1$ 条边的权重之和，该和在所有不构成树的 $n - 1$ 条边集合中取最小值。

首先，你想算出这一数值；至于它究竟意味着什么，你打算在回家的路上再细细琢磨。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph, respectively.

The $i$-th of the following $m$ lines contains three integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i \ne v_i \le n$, $1 \le w_i \le 10^9$) — the description of the $i$-th edge.

It is guaranteed that the graph does not contain self-loops or multiple edges.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$, and the sum of $m$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the minimum sum of weights of a set of $n - 1$ edges that does not form a tree, if such a set exists. Otherwise, print $-1$.

对于每个测试用例，输出一个整数——即不构成树的 $n - 1$ 条边的权重之和的最小值（如果这样的边集存在）；否则输出 $-1$。

In the first test case, you can choose the second, third and sixth edge, with a weight sum of $4 + 1 + 5 = 10$. It can be verified that this set of edges do not form a tree.

In the second test case, all possible subsets of $3$ edges will form a tree. Hence, there is no solution.

在第一个测试用例中，你可以选择第二、第三和第六条边，其权重之和为 $4 + 1 + 5 = 10$。可以验证，该边集不能构成一棵树。

在第二个测试用例中，所有可能的包含 $3$ 条边的子集均会构成一棵树。因此，不存在满足条件的解。