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.

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 $ .

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 $ .

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.