New update is available. Click here to update.

Minimum Travel Cost

Posted: 23 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninjaland is a country having 'N' states numbered from 1 to 'N'. These 'N' states are connected by 'M' bidirectional roads. Each road connects to different states and has some cost to travel from one state to another. Now, the chief wants you to select 'N' - 1 roads in such a way that the tourist bus can travel to every state at least once at minimum 'COST'.

For example :
Consider a country having 4 states numbered from 1 to 4. These 4 states are connected by 5 bidirectional roads given as :
1 --- 2 with cost = 8
2 --- 3 with cost = 6
3 --- 4 with cost = 5
1 --- 4 with cost = 2
1 --- 3 with cost = 4

The map of the country can be represented as:

Now, the best way to choose 3 roads is:

The cost of travelling from any state to all other states is  2 + 4 + 6 i.e. 12.
Input format :
The first line contains an integer 'T' denoting the number of test cases or queries to be run. 

The first line of each test case or query contains two space-separated integers 'N' and ‘M’ representing the number of states and number of roads in the country, respectively. 

The next 'N' lines of every test case contain three single space-separated integers ‘A’, ‘B’ and ‘C’, representing a road between the states 'A' and 'B' and 'C' denoting the cost of travelling them.
Output format:
For each test case, print 'N' - 1 lines each containing 3 space separated integers 'A', 'B' and 'C' representing the road you have chosen and the cost to traverse that road.
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