P14620 [2019 KAIST RUN Fall] Minimum Diameter Spanning Tree

给定一个具有 $N$ 个节点和 $M$ 条边的简单连通无向加权图 $G$。每个节点编号为 $1$ 到 $N$。 $G$ 的一棵生成树是 $G$ 的一个子图，它是一棵树并且连接了 $G$ 的所有顶点。一棵树的直径是树中任意两个节点之间的路径中最长路径的长度。$G$ 的一棵最小直径生成树是 $G$ 的生成树中直径最小的那棵。 请编写一个程序，找出任意一棵最小直径生成树。

输入的第一行包含两个整数 $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$ 的双向边。 保证给定的图没有任何自环或多重边，并且图是连通的。

第一行输出 $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$ 的双向边。 如果有多个可能的答案，输出其中任意一个。

翻译由 DeepSeek V3 完成