该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

有${N(2≤}$${N≤}$${2000)}$个农场，${M(1≤}$${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}$