Tour de France

The organisers of the Tour de France want the shortest possible route through the French cities they have selected. The route has to be a tour. It starts in one city, visits every other city exactly once, returns to the starting city, and each stage begins in the city where the previous stage ended.

Finding a shortest tour through an arbitrary road network is the travelling salesman problem, and the number of planned stages is far too large for that. So the organisers added one restriction. Every city offers at most two other cities as a destination, and every city accepts an incoming route from at most two cities. In graph terms the road network is a directed graph in which every vertex has out-degree at most $2$ and in-degree at most $2$.

Roads are one-way. A road from city $a$ to city $b$ does not imply a road in the other direction, and when both exist their lengths can differ.

Given such a graph, compute the total length of the shortest tour that visits every city exactly once and returns to its starting city.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 50$). Each test case has the following format.

• One line with two space-separated integers $N$ and $M$: the number of cities ($3 \le N \le 36$) and the number of roads ($N \le M \le 2N$).
• $M$ lines, each with three space-separated integers $i$, $j$ and $d$ ($0 \le i, j < N$, $i \ne j$, $1 \le d \le 10000$), meaning there is a one-way road of length $d$ from city $i$ to city $j$.

For any ordered pair $(a, b)$ at most one road from $a$ to $b$ is given, but the reverse road from $b$ to $a$ may also appear with a different length. Every city is the start of at most two roads and the end of at most two roads. Every test case admits at least one tour.

For each test case, print one line with the length of the shortest tour through all $N$ cities.