Minimum Spanning Tree Sum

You are given an undirected, weighted graph consisting of ‘N’ vertices and ‘M’ edges. Your task is to select 'N' - 1 edge such that a path exists between each pair of vertices and the weight of the spanning tree of the graph is minimum.

A minimum spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible sum of the weight of edges.

For Example :

Consider a graph having 4 vertices. These 4 vertices are connected by 5 bidirectional edges given as :
1 --- 2 with weight = 8
2 --- 3 with weight = 6
3 --- 4 with weight = 5
1 --- 4 with weight = 2
1 --- 3 with weight = 4

Now, the best way to choose 3 edges is:
2 --- 3 with weight = 6
1 --- 4 with weight = 2
1 --- 3 with weight = 4
The weight of the minimum spanning tree is 2 + 4 + 6, i.e., 12.

Input format :

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

The first line of each test case or query contains two space-separated integers 'N' and ‘M’ representing the number of vertices and edges in the graph. 

The next 'N' lines of every test case contain three single space-separated integers ‘A’, ‘B’ and ‘C’, representing an edge between the vertices 'A' and 'B' and 'C' denoting the weight of the edge.

Output Format:

For each test case, print N - 1 line each containing 3 space-separated integers 'A', 'B', and 'C' representing the edge you have chosen and the weight to traverse that edge.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10
1 <= 'N' <= 1000
N - 1 <= 'M' <= 2000
1 <= 'C' <= 10^6 

Time limit: 1 sec