Description

There is a city map where the vertices represent cities, and the undirected edges represent the connectivity between two cities. The weight on each edge indicates the cost of building a highway between the two cities. Research has revealed a characteristic of this map: every pair of cities is connected. The current problem is to build several highways to connect all the cities. The question is: how should the highways be designed to minimize the total cost of the project?

Input Format

n (number of cities, 1 < n ≤ 100)
e (number of edges)
The following e lines each contain three numbers: $i, j, w_{ij}$, representing the cost of building a highway between cities i and j.

Output Format

n-1 lines, each line containing the indices of two cities, indicating that a highway should be built between these two cities.

5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8

1  2
2  3
3  4
3  5