City Bus Network Construction

Problem Background

Special for beginners, ^_^

Problem Description

There is a city map in which the vertices are cities, undirected edges represent the connectivity between two cities, and the weight on an edge is the cost of building an expressway between those two cities. The study found that this map has one characteristic: every pair of cities is connected. The problem now is to build several expressways to connect all the cities. How should the design be made so that the total construction cost is minimized?

Input Format

$n$ (number of cities, $1 < n \le 100$)

$e$ (number of edges)

The following $e$ lines each contain $3$ numbers $i, j, w_{ij}$, representing the cost $w_{ij}$ of building an expressway between city $i$ and city $j$.

Output Format

$n-1$ lines, each containing the numbers of two cities, indicating that an expressway is built between these two cities.

Sample Input

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

Sample Output

1  2
2  3
3  4
3  5

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.