# Victor and World

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

## Description

After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are $n$ countries on the earth, which are numbered from $1$ to $n$. They are connected by $m$ undirected flights, detailedly the $i$-th flight connects the $u_i$-th and the $v_i$-th country, and it will cost Victor's airplane $w_i$ L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country.

Victor now is at the country whose number is $1$, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.

## Input

The first line of the input contains an integer $T$, denoting the number of test cases.
In every test case, there are two integers $n$ and $m$ in the first line, denoting the number of the countries and the number of the flights.

Then there are $m$ lines, each line contains three integers $u_i$, $v_i$ and $w_i$, describing a flight.

$1\leq T\leq 20$.

$1\leq n\leq 16$.

$1\leq m\leq 100000$.

$1\leq w_i\leq 100$.

$1\leq u_i, v_i \leq n$.

## Output

Your program should print $T$ lines : the $i$-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.

## Sample Input

1
3 2
1 2 2
1 3 3

## Sample Output

10

hujie

## Source

BestCoder Round #52 (div.2)