题目描述

牛们干草要用完了！贝茜打算去勘查灾情。

有 $N(2≤N≤2000)$ 个农场，$M(≤M≤10000)$ 条双向道路连接着它们，长度不超过 $10^9$。每一个农场均与农场 $1$ 连通。贝茜要走遍每一个农场。她每走一单位长的路，就要消耗一单位的水。从一个农场走到另一个农场，她就要带上数量上等于路长的水。请帮她确定最小的水箱容量。也就是说，确定某一种方案，使走遍所有农场通过的最长道路的长度最小，必要时她可以走回头路。

输入格式

第 $1$ 行输入两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行输入三个整数，表示一条道路的起点终点和长度。

输出格式

输出一个整数，表示在路线上最长道路的最小值。

3 3
1 2 23
2 3 1000
1 3 43

43

由 $1$ 到达 $2$，需要经过长度 $23$ 的道路；回到 $1$ 再到 $3$，通过长度 $43$ 的道路。最长道路为 $43$。