City Road Renovation Decision

In a bustling metropolis, the road network is extremely congested. The city has \(n\) intersections connected by \(m\) bidirectional roads, and every pair of intersections is connected by at most one road. Each road has a score \(w\); a smaller score means the road is busier and in greater need of renovation. Due to a limited budget, the mayor wants to renovate as few roads as possible such that:

• The renovated roads connect all intersections.
• The number of renovated roads is minimized (i.e. exactly \(n-1\) roads are chosen).
• Among all choices satisfying the above, the maximum score among the renovated roads is as small as possible.

Your task as the urban planner is to choose an optimal set of roads to renovate. If there are multiple solutions, any one will be accepted.

inputFormat

The first line contains two integers \(n\) and \(m\) (number of intersections and number of roads), separated by a space.

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) describing a road between intersections \(u\) and \(v\) with score \(w\> (1-indexed). The graph is guaranteed to be connected.

outputFormat

Output the optimal decision as follows:

1. On the first line, output a single integer representing the minimum possible maximum road score among the chosen roads.
2. Then output exactly \(n-1\) lines. Each line should contain two integers \(u\) and \(v\) representing a road selected for renovation.

If there are multiple valid answers, any one is acceptable.

sample

4 4
1 2 3
2 3 5
3 4 4
1 4 6

5
1 2
3 4
2 3