P5304 [GXOI/GZOI2019] 旅行者

J 国有 $n$ 座城市，这些城市之间通过 $m$ 条单向道路相连，已知每条道路的长度。 一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。 为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。 也许下面的剧情你已经猜到了—— Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

无

无

### 样例解释 对于第一组数据，$1$ 到 $3$ 最短路为 $5$；$1$ 到 $6$ 最短路为 $7$；$3,6$ 无法到达，所以最近的两点为 $1,3$，最近的距离为 $5$。 对于第二组数据，$1$ 到 $2$ 最短路为 $6$；$5$ 到 $3$ 最短路为 $6$；其余的点均无法互相达，所以最近的两点为 $1,2$ 和 $5,3$，最近的距离为 $6$。 ### 数据范围 $2 \le k \le n$，$1 \le x,y \le n$，$1 \le z \le 2 \times 10^9$，$T \leq 5$。 |测试点编号|$n$ 的规模|$m$ 的规模|约定| |:-:|:-:|:-:|:-:| |$1$|$\le 1,000$|$\le 5,000$|无| |$2$|$\le 1,000$|$\le 5,000$|无| |$3$|$\le 100,000$|$\le 500,000$|保证数据为有向无环图| |$4$|$\le 100,000$|$\le 500,000$|保证数据为有向无环图| |$5$|$\le 100,000$|$\le 500,000$|保证数据为有向无环图| |$6$|$\le 100,000$|$\le 500,000$|无| |$7$|$\le 100,000$|$\le 500,000$|无| |$8$|$\le 100,000$|$\le 500,000$|无| |$9$|$\le 100,000$|$\le 500,000$|无| |$10$|$\le 100,000$|$\le 500,000$|无| 2024-12-18 管理员注：[在测试点五中可能存在自环](https://www.luogu.com.cn/discuss/1022672)。