SP1479 PT07C - The GbAaY Kingdom

给定一个 $n$ 个点 $m$ 条边的带权无向图. 现求一生成树,使得任意两结点间最长距离(直径)最短.

输入的第一行包含两个正整数 $n,m (1 \le n \le 200,n - 1 \le m \le 20000)$ ,代表点数和边数. 接下来 $m$ 行每行三个正整数 $u,v,w$,代表一条从 $u$ 连向 $v$ 边权为 $w$,保证 $u \ne v,1 \le w \le 10^5$

输出第一行包含一个整数，表示生成树直径. 接下来输出 $n - 1$ 行,每行两个数代表生成树的一条边. 如果有多解,输出任意一个. ### 输入输出样例 #### 输入 #1 ``` 3 3 1 2 1 2 3 1 1 3 1 ``` #### 输出 #1 ``` 2 1 2 1 3 ```