Network (solution through graphs)

NEERC, Northern Quarter-finals, 2001.

The task

Andrey works as a system administrator and plans to create a new network in his company. In total there will be N hubs, they will be connected to each other using cables.

Since every company employee must have access to the entire network, every hub must be reachable from every other hub — perhaps through several intermediate hubs. Since there are different types of cables and short cables are cheaper, you need to make such a network plan (hub connections) so that the maximum length of one cable is as short as possible. There is another problem - not every pair of hubs can be directly connected due to compatibility issues and the geometric constraints of the building. Andrei will provide you with all the necessary information about possible hub connections.

You must help Andrew find a way to connect the hubs, which will satisfy all the above conditions.

Input

The first line of the input file contains two integers: N - the number of hubs in the network (2 <= N <= 1000) and M - the number of possible connections of the hubs (1 <= M <= 15 000).

All hubs are numbered from 1 to N. The next M lines contain information about possible connections — the numbers of two hubs that can be connected, and the length of cable that is required to connect them. This length is a positive integer not exceeding 10 ⁶ . There is no more than one way to connect each pair of hubs. The hub cannot be attached to itself. There is always at least one way to connect all the hubs.

Conclusion

First output the maximum length of a single cable in your connection plan (this is the amount you need to minimize). Then output your plan: first output P - the number of cables you used, then output P pairs of integers - the numbers of the hubs that are directly connected in your plan by cables.

  Input Example Output Example
 4 6 1
 1 2 1 3
 1 3 1 1 2
 1 4 2 1 3
 2 3 1 3 4
 3 4 1                 
 2 4 1

Decision

We give a brief formalization of the problem statement. For a given weighted graph, find a spanning tree so that the maximum of the weights of the edges of this border tree is minimal, and derive this weight, the number of edges in the spanning tree and the edges themselves (the number of vertices connected by the corresponding edge).

By constructing a minimum spanning tree using the Kruskal algorithm, it turns out that it is always the solution to the problem. Thus, the solution of the problem is reduced to finding the minimum spanning tree by the Kruskal algorithm, and then to finding the maximum weight of the edges included in it.

Formal description

  Network ()
 1. Read the list of graph edges from a file.
 2. Sort the edges of the graph in ascending order of their weight (pipe prices).
 3. Use the Kruskal algorithm to find the smallest skeleton. 
    tree (perform paragraphs 3.1-3.4):
    3.1.  Initialize the value of the number of cables to zero.
    3.2.  Select the first edge of the graph in the list.
    3.3.  Until all edges of the graph have been viewed, repeat paragraphs.  3.3.1-3.3.3:
         3.3.1.  If the vertices of the current edge are not in the same component 
                connectivity, then add an edge to the smallest skeleton tree.
         3.3.2.  If the edge has been added, then increase the amount 
                cables on 1.
         3.3.3.  Jump to versed edge.
    3.4.  Read the length of the last added edge by the maximum length
         cable.
 4. Print the number of used cables and the maximum cable length.
 5. Derive all edges that belong to the minimum skeleton tree.

The initial network and the shortest stem tree derived from it.
The last added edge ([8; 9], length 11) is the longest cable in the constructed network.