Minimum Difficulty Round Trip

You are given a set of checkpoints connected by bidirectional routes, where each route has an associated difficulty. Starting at checkpoint 1, your task is to visit every other checkpoint exactly once and return to the starting point. The goal is to find the route that minimizes the total difficulty.

The total difficulty of a route can be mathematically expressed as:

$$D_{total} = \sum_{i=0}^{n} d_i$$

where \(d_i\) is the difficulty of moving from one checkpoint to the next.

If it is impossible to complete such a trip, output -1.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains an integer \(N\) (\(2 \leq N \leq 10\)) representing the number of checkpoints.
• The next line contains an integer \(M\) representing the number of routes.
• Each of the following \(M\) lines contains three integers \(A\), \(B\), and \(D\) (\(1 \leq A, B \leq N\) and \(D \geq 1\)), indicating a bidirectional route between checkpoints \(A\) and \(B\) with difficulty \(D\).

Input is given through standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum total difficulty required to complete the round trip. If the trip is impossible, output -1.

Output is printed through standard output (stdout).

## sample

2
4
5
1 2 10
2 3 10
3 4 10
4 1 10
1 3 15
3
3
1 2 7
2 3 8
1 3 12

40
27

</p>