PT07C - The GbAaY Kingdom

no tags 

Jiajia is the king of the GbAaY Kingdom. He always squeezes his 20 ministers as coolies. There are n cities and m two-way 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 <= 105). 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: 2013-04-11 15:02:22

can some one help me pls...
for the test case say
4 5
1 4 4
1 3 7
1 2 2
2 4 1
2 3 1
output
3
2 3
2 4
1 2
or
the paths in that max range path like
3
1 2
2 4

Last edit: 2013-07-06 18:39:26
himanshu jain: 2012-09-16 15:21:17

can we do this problem using mst algo's?

Graphis_: 2011-05-08 02:27:48

Last edit: 2011-11-10 00:50:39

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:0.162s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Co-author Amber