Play with Trees

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 cost of fuel, he wants to simplify the road system in the GbAaY Kingdom. Thus, some roads will be removed. But he requests the ministers to 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⁵). 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 a 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