【问题描述】

Farmer John 有 N 个农场，编号为 1 ~ N。M 条双向通行的道路把这些农场连在一起，任意两个农场可以互达。每天道路有一个长度。

由于道路太多，奶牛们经常迷路。所以 John 打算封锁一些道路。

封锁哪些道路呢？John 看着眼前的交通图陷入了沉思。

John 希望封锁尽可能多的道路，但仍要保证任意两个农场可以互达。

在封锁尽可能多的道路前提下，John 还希望，封锁道路完成后，在新的交通图上，距离最远的两个农场间的距离尽可能小。

John 想要知道这个最小距离是多少？

你能帮助他吗？

注：两个农场间的距离指从一个农场到达另一个农场所经过的道路长度之和。

【输入格式】

第一行：两个整数 N，M

接下来 M 行，每行三个整数 u，v，w，表示农场 u 和农场 v 之间有一条长度为 w 的双向道路。

【输出格式】

一个整数，表示最小距离。

3 3
1 2 0
2 3 1
3 1 2

1

【数据范围】

100% 的数据：1 <= N < = 100, 0 < M < = 1000, 1 <= u, v <= N, 0 < = w < = 1000