Skills Training 3

For Vincent's birthday his parents bought him a city.

The city has \(N\) houses numbered 1 to \(N\), with \(M\) roads, each having a length of \(K\)_i. However Vincent hates inefficiency, so he decides to remove all extra roads while keeping the city entirely connected (he does not realize this makes the travel slower).

Determine the configuration of roads given \(N\), \(M\), and each of the \(M\) roads.

Input Specification:

The first line will contain \(N\) and \(M\)

The next \(M\) lines will contain the starting building number of the road, the ending building number, and \(K\)_i.

Output Specification:

Output each of the roads in order from shortest to longest in the final city, and -1 if it is not possible, see sample output below.

TIME CONSTRAINT: 1s

Sample Input:

4 4
1 2 5
1 3 6
2 3 7
3 4 8

Sample Output:

1 2
1 3
3 4