[Usaco2005 Mar]Out of Hay 干草危机

牛们的干草即将耗尽，贝茜打算前往其他农场勘查干草储备情况。

共有 $N$ 个农场，编号为 $1$ 到 $N$，农场之间由 $M$ 条双向道路连接。贝茜从农场 $1$ 出发，需要走遍所有农场。两个农场之间可能有多条长度不同的道路，且所有农场都与农场 $1$ 连通。

贝茜每经过单位长度的道路，就需要消耗一单位水。她可以在每个农场补充水，因此水箱所需的容量只取决于行程中经过的最长道路。她可以自行选择行走路线，也可以在必要时沿道路返回。

请确定一种能够走遍所有农场的路线，使其中经过的最长道路尽可能短，并输出该道路的长度。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$，分别表示农场数量和道路数量。

接下来 $M$ 行，第 $i$ 行包含三个以空格分隔的整数 $A_i$、$B_i$ 和 $L_i$，表示农场 $A_i$ 与农场 $B_i$ 之间有一条长度为 $L_i$ 的双向道路。

输出格式

输出一个整数，表示走遍所有农场时，所经过的最长道路长度的最小值。

样例输入

3 3
1 2 23
2 3 1000
1 3 43

样例输出

43

样例解释

贝茜先从农场 $1$ 经过长度为 $23$ 的道路到达农场 $2$，再返回农场 $1$，然后经过长度为 $43$ 的道路到达农场 $3$。行程中经过的最长道路长度为 $43$。

数据范围

• $2\le N\le 2000$；
• $1\le M\le 10^4$；
• 道路长度不超过 $10^9$；
• 所有农场均与农场 $1$ 连通；
• 两个农场之间可能存在多条长度不同的道路。

来源与许可

本题为 USACO 2005 March 试题「Out of Hay（干草危机）」，题面与测试数据整理自 BZOJ。

样例 1

输入

3 3
1 2 23
2 3 1000
1 3 43

输出

43