Weeping Fig

A weeping fig grows in your backyard. Its roots never push under the house, they only spread into the empty space around it, so your friends call it the nice weeping fig. A friend who is building a new house wants the same tree, and yours grows fast enough that you agreed to cut off part of it.

The tree has $N$ roots, numbered $1$ to $N$. There are $M$ connections, each one joining two different roots, and cutting the connection between roots $a$ and $b$ takes effort $w$.

You want to split the roots into two groups, neither of them empty. No connection may be left between the two groups, and the effort you spend is the sum of the efforts of the connections you cut. Find the smallest total effort.

The first line has the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case has two integers $N$ and $M$, the number of roots and the number of connections ($2 \le N \le 500$, $N-1 \le M \le N(N-1)/2$).

Each of the next $M$ lines has three integers $a_i$, $b_i$, $w_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le w_i \le 1000$), meaning roots $a_i$ and $b_i$ are connected and cutting that connection takes effort $w_i$.

At most one connection joins any pair of roots, and every root reaches every other root along the connections.

For each test case, print the smallest total effort on its own line.

In the first example, pulling root $1$ away from the rest takes $2+3+5=10$. Splitting $\{1,2\}$ from $\{3,4\}$ instead takes $3+5+5+5=18$.