Migrated from Lutece 2729 摆摆国的道路修复

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上接《刺杀卷卷国王》

在卷卷国王遇刺后，卷卷国与摆摆国协议停战，两国开始友好建交。

摆摆国的城市有 $n$ 个节点，$m$ 条道路，每条道路长度为 $val_{i}$ 。由于战争，城市里所有的道路都被不同程度破坏了，摆摆国计划修复一些被破坏的道路，使得城市中的所有节点都能相互到达。又由于战争造成的资金短缺，他们只能修复 $n-1$ 条道路。同时摆摆国希望在道路修建好后，尽可能减小距离最远的两个节点之间的距离。作为摆摆国的城市规划师，摆摆国王把这个任务交给了你，并要求你告诉他在最优方案下距离最远的两个节点之间的距离。

Input

第一行读入 $n,m$ 表示节点和道路数。

接下来 $m$ 行读入边的信息。

其中第 $i$ 行读入三个整数，$u_{i},v_{i},val_{i}$ 分别表示第 $i$ 条边的两个节点和边的长度。

Output

输出距离最远的两个节点之间的距离。

Samples

8 10
1 2 10
2 3 20
3 4 15
4 1 30
4 8 1000
8 6 30
5 6 20
6 7 10
7 8 20
6 8 10

1065

Constraints

$n\le 500,\ n-1\le m\le \frac{n(n-1)}{2}$

$u_{i},v_{i}\le n,\ val_{i}\le 10^{9}$

Note

数据不保证无重边和自环

Resources

2022 UESTC ICPC Training for Graph