Minimum Travel Cost Problem

You are given a country called 'Ninjaland' with 'N' states, numbered from 1 to 'N'. These states are connected by 'M' bidirectional roads, each with a specified travel cost. The aim is to select exactly 'N' - 1 roads so that a tourist bus can travel to every state at least once, minimizing the total travel cost.

Example:

Input:

Consider a country with 4 states (1 to 4) and 5 bidirectional roads: 
1 --- 2, cost = 8
2 --- 3, cost = 6
3 --- 4, cost = 5
1 --- 4, cost = 2
1 --- 3, cost = 4

Output:

The optimal roads can be selected as follows:
1 --- 4, cost = 2
1 --- 3, cost = 4
2 --- 3, cost = 6
Total minimum travel cost = 12.

Constraints:

• 1 ≤ 'T' ≤ 10 (Number of test cases)
• 1 ≤ 'N' ≤ 1000 (Number of states)
• 'N' - 1 ≤ 'M' ≤ 2000 (Number of roads)
• 1 ≤ 'C' ≤ 106 (Cost of roads)
• Time limit: 1 sec

Input:

The first line contains an integer 'T'.
Each test case consists of:
- An integer 'N' and 'M'.
- 'M' lines, each containing three integers 'A', 'B', and 'C'.

Output:

For each test case, print 'N' - 1 lines, each containing three integers 'A', 'B', and 'C' indicating the chosen roads with their costs.

Note:

You do not need to manually print anything as it is handled by the system. Just implement the function to find the minimum cost selection of roads.