You are given a graph with ~N~ nodes and ~M~ edges. Find the path with minimum length that goes through every node exactly once, then returns to the starting node.

Solve this problem for ~T~ test cases.

Constraints

~T = 10000~

~N~ is equal across all test cases ~T~.

~N > 1~

~1 \leq M \leq \min(\frac{N(N-1)}{2}, 2 \times 10^5)~

~1 \leq u_i, v_i, w_i \leq N~

The sum of ~N~ across all test cases ~T~ is at most ~50000~.

Input Specification

The first line will contain a single integer ~T~.

There will then be ~T~ test cases. Each test case will contain two space-separated integers ~N~ and ~M~ on the first line, followed by ~M~ lines each containing three space-separated integers ~u_i~, ~v_i~, and ~w_i~, denoting an edge of length ~w_i~ from ~u_i~ to ~v_i~.

Output Specification

For each test case, output a single integer denoting the minimum length of a path that traverses every node then returns to the starting node. If no such path exists, print -1.

Sample Input

1
5 10
1 5 2
3 3 1
4 5 3
4 4 5
3 2 1
4 2 1
5 5 2
1 3 4
5 4 4
2 4 3

Sample Output

11

Explanation for Sample

The shortest path that fulfills the requirement has length ~11~. Note that this sample is provided for clarity, and the actual test data will have ~T = 10000~.