题目描述

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

有$\red{N(2≤}$$\red{N≤}$$\red{2000)}$个农场，$\red{M(1≤}$$\red{M≤}$$\red{10000)}$条双向道路连接着它们，长度不超过$\red{10^9}$．每一个农场均与农场$\red{1}$连通．贝茜要走遍每一个农场．她每走一单位长的路，就要消耗一单位的水．从一个农场走到另一个农场，她就要带上数量上等于路长的水．

请帮她确定最小的水箱容量．也就是说，确定某一种方案，使走遍所有农场通过的最长道路的长度最小，必要时她可以走回头路．

输入格式

第$\red{1}$行输入两个整数$\red{N}$和$\red{M}$;

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

输出格式

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

样例

输入样例

3 3
1 2 23
2 3 1000
1 3 43

输出样例

43

提示

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