题目描述

克索尼亚所在的城市由 $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)$ 值。

4 0
1 2 1
1 3 2
2 3 3
2 4 3

6

提示

样例说明

第一个样例的说明：

$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 完成