Russian Translation Available

You are given a weighted graph with N vertices and M edges. Find the total weight of its maximum spanning tree.

Input

The first line contains one integer T denoting the number of test cases. Each test case starts with a line containing 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes weight of this edge.

Output

For each test case output one integer - the total weight of its maximum spanning tree.

Constraints

• 1 <= T <= 20
• 1 <= N <= 5000
• 1 <= M <= 100 000
• 1 <= c <= 10 000