题目描述

You are given a simple connected undirected weighted graph $G$ with $N$ nodes and $M$ edges. Each node is numbered 1 through $N$.

A spanning tree of $G$ is a subgraph of $G$, which is a tree and connects all the vertices of $G$. The diameter of a tree is the length of the longest path among the paths between any two nodes in the tree. A minimum diameter spanning tree of $G$ is a spanning tree of $G$ that has a minimum diameter.

Write a program that finds any minimum diameter spanning tree.

输入格式

The first line of the input contains two integers $N$ ($2 \le N \le 500$) and $M$ ($N-1 \le M \le \frac{N(N-1)}{2}$).

Then $M$ lines follow: The $i$ ($1 \le i \le M$)-th line contains three space-separated integers $u_i$, $v_i$ and $l_i$ ($1 \le u_i, v_i \le N$, $1 \le l_i \le 10^9$); it describes a bidirectional edge connecting vertex $u_i$ and vertex $v_i$ with length $l_i$.

It is guaranteed that the given graph doesn't have any loops or multiple edges, and the graph is connected.

输出格式

In the first line, print the diameter of the minimum diameter spanning tree of $G$.

In the next $N-1$ lines, print the description of the edges in the minimum diameter spanning tree of $G$. The $j$ ($1 \le j \le N-1$)-th line should contain two space-separated integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le N$); it describes a bidirectional edge connecting vertex $x_i$ and $y_i$.

If there are several possible answers, print any one of them.

3 3
1 2 1
2 3 1
3 1 1

2
1 2
3 1

6 7
1 2 10
2 3 20
1 3 30
3 4 1000
4 5 30
5 6 20
4 6 10

1060
3 4
6 4
5 6
2 3
1 2