Edge Reverse

Description:

Input:

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

Each test case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the number of nodes in the graph and the number of edges in the graph.

The next $$$m$$$ lines of each test case contain $$$3$$$ integers each — $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$), indicating an edge from $$$u$$$ to $$$v$$$ with a weight of $$$w$$$. It is guaranteed that no edge connects a vertex to itself, and no pair of edges share the same origin and destination simultaneously.

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

Output:

For each test case, output the minimum cost. If there is no solution, print $$$-1$$$.

Sample Input:

4
2 1
1 2 3
5 4
1 2 10
2 3 10
3 1 10
4 5 10
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 500
4 3 20
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 5
4 3 20

Sample Output:

0
-1
20
5

Note:

In the first test case, an edge exists from $$$1$$$ to $$$2$$$, so all nodes are reachable (from $$$1$$$).

In the second test case, no nodes are reachable from any node no matter what edges we reverse, so the answer is $$$-1$$$.

In the third test case, reversing the $$$4$$$-th or $$$5$$$-th edge allows all nodes to be reachable from $$$1$$$. We choose the $$$5$$$-th edge here because its weight is smaller.