You are given a weighted undirected graph with numVertices vertices, indexed 0 to numVertices - 1.
The graph has numEdges edges, each with a source, destination and weight.

A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.

Find the total edge weight of a valid MST of the graph using Prim's algorithm.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains two space-separated integers numVertices and numEdges.
• The next numEdges lines descibes the edges of the graph with three space-separated integers - source, destination and weight.

Output Format

For each test case, the output has one line with the total edge weight of MST.

Sample Input

4
7 8
0 1 2
0 3 3
0 6 4
1 2 3
1 4 2
3 4 5
4 5 7
4 6 6
3 3
0 1 2
1 2 3
0 2 4
3 2
0 1 2
1 2 3
1 1
0 0 2

Expected Output

21
5
5
0

Constraints

1 <= T <= 20
1 <= numVertices <= 500
0 <= numEdges <= 100000
1 <= weight <= 100