ZOJ Problem Set - 1542
Andrew is working as system administrator and is planning to establish a new
network in his company. There will be N hubs in the company, they can be connected
to each other using cables. Since each worker of the company must have access
to the whole network, each hub must be accessible by cables from any other hub
(with possibly some intermediate hubs).
The first line of the input file contains two integer numbers: N - the number of hubs in the network (2 <= N <= 1000) and M - the number of possible hub connections (1 <= M <= 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can be connected and the cable length required to connect them. Length is a positive integer number that does not exceed 10^6. There will be no more than one way to connect two hubs. A hub cannot be connected to itself. There will always be at least one way to connect all hubs.
Process to the end of file.
Output first the maximum length of a single cable in your hub connection plan (the value you should minimize). Then output your plan: first output P - the number of cables used, then output P pairs of integer numbers - numbers of hubs connected by the corresponding cable. Separate numbers by spaces and/or line breaks.
Source: Northeastern Europe 2001, Northern Subregion