P15043 [UOI 2022 II Stage] 图

克索尼亚所在的城市由 $n$ 个交叉路口组成，这些路口之间通过 $n$ 条双向道路连接。 交叉路口编号为 $1$ 到 $n$。道路也编号为 $1$ 到 $n$。第 $i$ 条道路连接编号为 $a_i$ 和 $b_i$ 的交叉路口，其长度为 $c_i$。 已知，通过现有道路可以从任何一个交叉路口到达任何其他交叉路口。任意两个交叉路口之间最多有一条道路。没有连接同一交叉路口的道路。 定义 $dist(x, y)$ 为交叉路口 $x$ 和 $y$ 之间最短路径的长度。 克索尼亚希望找到城市中的两个交叉路口 $u$ 和 $v$，使得 $dist(u, v)$ 在所有可能的 $u, v$ 对中是最大的。

第一行包含两个整数 $n$ 和 $g$ ($3 \leq n \leq 200\,000$, $0 \leq g \leq 5$) —— 分别表示城市中的交叉路口数量和测试组编号。 接下来的 $n$ 行，每行包含三个整数 $a_i$、$b_i$、$c_i$ ($1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq 10^9$)。 保证使用道路可以从任何一个交叉路口到达任何其他交叉路口。 保证没有连接同一交叉路口的道路。 保证任意两个交叉路口之间最多有一条道路。

输出所有交叉路口对 $u, v$ 中最大的 $dist(u, v)$ 值。

### 样例说明 第一个样例的说明： $dist(1, 2) = 1$ $dist(1, 3) = 2$ $dist(1, 4) = 4$ $dist(2, 3) = 3$ $dist(2, 4) = 3$ $dist(3, 4) = 6$ 因此，最大的 $dist(u, v) = 6$。 ### 评分细则 - （22 分）： 图的结构为一个简单环。 - （17 分）： $n \leq 200$。 - （24 分）： 图中每个环的长度不超过 1000。 - （9 分）： $c_i = 1$。 - （28 分）： 无额外限制。 翻译由 DeepSeek V3 完成