13367번 - Weeping Fig 다국어

“Roots grow rapidly, invading gardens, growing under and lifting sidewalks, patios, and driveways.” - United States Forest Service

Because of that, it is not recommend to be planted in residential household. However, you happen to have one in your backyard, and your fig is very nice — it does not invade any part of your household at all. It just expands into empty space around the house.

Your friend are constructing a new house, and want to have a weeping fig in his backyard too. But he is scared that traditional weeping fig could destroy his home, so he wants your weeping fig (which is now known among your friends to be a “nice weeping fig.”) Since the tree grows rapidly, you decided to just cut parts of your tree for your friend.

Even though just only one root is enough for your friend to have the same nice tree as you, it is not easyseparating one root since it has many connections to other roots. Specifically, each root has many connections to some other roots, with no pattern. Each root connection also vary in diameter, thus the effort required for separating is not constant.

Given the number of roots, its connection and connection separation effort, please find the minimal effort required to separate your weeping fig into two entities.

First line has the number of test cases, T (1 ≤ T ≤ 20)

For each test case, the first line contains two integers N M specifying the number of roots and number of connection (1 ≤ N ≤ 500, N-1 ≤ M ≤ (N² -N)/2)

Following M lines contain three integer a_i b_i w_i (1 ≤ a_i , b_i ≤ N, 1 ≤ w_i ≤ 1000) indicating that there is a root connection from root a_i to root b_i that requires effort w_i to separate. It is guaranteed that the input will form single weeping fig tree only.

For each test case, output the minimal effort required on its own line.

Explanation

You can split the node 1 from the rest, which takes 10 effort. If you instead split 12 and 34, you would have 8 + 10 = 18 effort.