题目描述

傍晚，小奇家的电话响了，听筒里传来带队教练着急的声音：“请问是小奇的家长吗？这孩子又没来集训，是不打算参加测验了吗？”一听要测验，小奇的父母坐不住了，决定立刻出门把他找回来。凭以往的经验，小奇这会儿准是躲在好友阿珍或阿强家里打游戏。父母撂下电话就出了门。

小奇居住的城区由 $N$ 个居住点和若干条连接居住点的双向街道组成，经过街道 $x$ 需花费 $T_{x}$ 分钟。可以保证，任意两个居住点间有且仅有一条通路。小奇家在点 $C$，阿珍和阿强分别住在点 $A$ 和点 $B$。教练和小奇的父母都有城区地图，但小奇的父母知道点 $A$、$B$、$C$ 的具体位置，而教练不知道。

为了尽快找到小奇，他的父母会遵守以下两条规则：

1. 如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，那么小奇的父母先去阿珍家寻找小奇，如果找不到，再去阿强家；反之亦然。
2. 小奇的父母总沿着两点间唯一的通路行走。

显然，教练知道小奇的父母在寻找过程中会遵守以上两条规则，但由于他并不知道 $A$、$B$、$C$ 的具体位置，所以现在他希望你告诉他，最坏情况下小奇的父母要耗费多长时间才能找到小奇？

输入格式

输入文件第一行是两个整数 $N$ 和 $M$，分别表示居住点总数和街道总数。

以下 $M$ 行，每行给出一条街道的信息。第 $i+1$ 行包含整数 $U_{i}$、$V_{i}$、$T_{i}$，表示街道 $i$ 连接居住点 $U_{i}$ 和 $V_{i}$，并且经过街道 $i$ 需花费 $T_{i}$ 分钟。街道信息不会重复给出。

输出格式

输出文件仅包含整数 $T$，即最坏情况下小奇的父母需要花费 $T$ 分钟才能找到小奇。

样例

4 3
1 2 1
2 3 1
3 4 1

4

提示

对于 $100\%$ 的数据，$3 \le N \le 2\times 10^5$，$1 \le U_{i},V_{i} \le N$，$0 \le T_{i} \le 10^{9}$。