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 ```

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 of the oil fee, he want to simplify the road system in the GbAaY Kingdom to save the traffic cost. Thus, some of roads will be removed. But he requests the ministers 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.

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 $ ^{5} $ ). They denote there is a road with length _w_ between city _u_ and city _v_.

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 an road between city _u_ and city _v_ in the simplification plan. If there are many optimal solutions, any of them will be accepted.

3 3
1 2 1
2 3 1
1 3 1

2
1 2
1 3