PT07C  The GbAaY Kingdom
Jiajia is the king of the GbAaY Kingdom. He always squeezes his 20 ministers as coolies. There are n cities and m twoway roads connecting cities in the kingdom. Because of the increasing of the oil fee, he want to simplify the road system in the GbAaY Kingdom to save the traffic cost. Thus, some of roads will be removed. But he requests the ministers guarantee that there is always a path between any two cities. GbAaY Minister Loner suggests Jiajia for the convenience of the traffic management, the farthest distance between cities should be minimal. Unhesitatingly, Jiajia agrees this resolution. As the GbAaY Kingdom's minister (cooly), you must work hard for Jiajia to make the simplification plan.
Input
The first line contains two integers n, m (1 <= n <= 200, n  1 <= m <= 20000). Each line of the following m lines contains three integers u, v, w (u != v, 0 <= w <= 10^{5}). They denote there is a road with length w between city u and city v.
Output
The first line contains one integer which is the farthest distance between cities after the simplification. Each line of the follow n  1 contains two integers u, v (u < v). They denote there is an road between city u and city v in the simplification plan. If there are many optimal solutions, any of them will be accepted.
Example
Input: 3 3 1 2 1 2 3 1 1 3 1 Output: 2 1 2 1 3
hide comments
_maverick:
20130411 15:02:22
can some one help me pls...


himanshu jain:
20120916 15:21:17
can we do this problem using mst algo's? 

Graphis_:
20110508 02:27:48
Last edit: 20111110 00:50:39 
Added by:  ThanhVy Hua 
Date:  20070407 
Time limit:  0.162s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  Coauthor Amber 