Description

给定一个具有 $N$ 个节点和 $M$ 条边的简单连通无向加权图 $G$。每个节点编号为 $1$ 到 $N$。

$G$ 的一棵生成树是 $G$ 的一个子图，它是一棵树并且连接了 $G$ 的所有顶点。一棵树的直径是树中任意两个节点之间的路径中最长路径的长度。$G$ 的一棵最小直径生成树是 $G$ 的生成树中直径最小的那棵。

请编写一个程序，找出任意一棵最小直径生成树。

Input Format

输入的第一行包含两个整数 $N$（$2 \le N \le 500$）和 $M$（$N-1 \le M \le \frac{N(N-1)}{2}$）。

接下来是 $M$ 行：第 $i$（$1 \le i \le M$）行包含三个以空格分隔的整数 $u_i$、$v_i$ 和 $l_i$（$1 \le u_i, v_i \le N$，$1 \le l_i \le 10^9$）；它描述了一条连接顶点 $u_i$ 和顶点 $v_i$、长度为 $l_i$ 的双向边。

保证给定的图没有任何自环或多重边，并且图是连通的。

Output Format

第一行输出 $G$ 的最小直径生成树的直径。

接下来的 $N-1$ 行，输出最小直径生成树中边的描述。第 $j$（$1 \le j \le N-1$）行应包含两个以空格分隔的整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le N$）；它描述了一条连接顶点 $x_i$ 和 $y_i$ 的双向边。

如果有多个可能的答案，输出其中任意一个。

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

Hint

翻译由 DeepSeek V3 完成