Minimum Direct Connections

You are given a city with m stations and k bidirectional routes connecting them. Each route connects two different stations and has an associated length.

Your task is to determine a set of direct connections such that every station is accessible from every other station. In other words, you need to construct a spanning tree of the graph. The selected connections must be one possible solution that would result in a Minimum Spanning Tree (MST), computed using Prim's algorithm.

The MST of a connected graph with m nodes always contains exactly m-1 edges, i.e. $m - 1$ connections.

If there are multiple valid MSTs, any one of them is acceptable.

inputFormat

The input is read from standard input (stdin) and has the following format:

m k
u1 v1 l1
u2 v2 l2
... 
uk vk lk

Where:

• m (1 ≤ m ≤ 10^5) is the number of stations.
• k (1 ≤ k ≤ 10^5) is the number of routes.
• Each of the next k lines contains three integers: ui and vi (the stations connected by the route) and li (the length of that route).

outputFormat

The output is written to standard output (stdout) and must have the following format:

n
u1 v1
u2 v2
...
u n v n

Where:

• n is the number of connections used (which should be exactly m - 1 if the network is connected).
• Each subsequent line contains a pair of integers indicating a direct connection between two stations in the MST.

## sample

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

5
1 3
3 2
2 5
3 4
3 6

</p>