Republic of Inhanica

The Republic of Inhanica is a country of $N$ islands numbered 1 to $N$. Travel between the islands used to be very hard, until the bridge designer Jin built the smallest possible number of bridges, each joining two islands, so that every island can be reached from every other one. There are therefore $N - 1$ bridges, and the islands and bridges form a tree.

Jin lives on island 1. One day he heard a dangerous rumor: the serial killer and master thief Lupin is hiding on one of the islands that has exactly one bridge, island 1 excluded, and is after Jin's life. Jin does not know which island that is, so he wants to cut every route from island 1 to every island other than island 1 that has exactly one bridge.

Blowing up a bridge takes dynamite, and the amount depends on the size of the bridge, so it differs from bridge to bridge. Dynamite is very expensive, so Jin wants to use as little of it as possible. Given the amount of dynamite needed for each bridge, find the minimum total amount of dynamite.

For the islands and per-bridge dynamite amounts in the figure, blowing up the bridges drawn in red keeps Jin safe from Lupin while using the least dynamite.

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

The first line of each test case contains the number of islands $N$ ($1 \le N \le 1000$) and the number of bridges $M$. The bridges are the smallest set that connects all islands, so $M = N - 1$.

Each of the next $M$ lines contains the numbers of the two islands that the bridge joins and the amount of dynamite $D$ ($1 \le D \le 20$) needed to blow up that bridge, separated by spaces.

For each test case, print the minimum total amount of dynamite on its own line. When $N = 1$ there is no bridge to blow up, so print 0.