马上就要比赛了，但是小K团队的题目还没出完，要赶快找到小K，大家都在想小K又去哪里摸鱼了。根据小K的喜好，他现在肯定呆在 $A$ 地或 $B$ 地摸鱼，小C住在$C$地。 小K所居住的城市里有 $N$ 个地点， 这些地点间有 $M$ 条双向街道相连，每两个地点见仅有一条道路。经过街道 $ei$ 需要 $ci$ 单位的时间。 现在小C有城市的地图，于是团队派小C去找小K，为了尽快找到小K，小C会遵循以下两条规则：

• 如果 $A$ 地 距离 $C$ 地 比 $B$ 地 距离 $C$ 地 近，那么小C就会先去 $A$ 地 找 小K， 如果找不到，再去 $B$ 地，反之亦然。
• 小C总沿着两点间唯一的通路行走。

但是由于除了小C团队里没人有地图，所以团队就不知道$A$, $B$, $C$三地的具体位置，他们想知道小C最坏情况下要花多长时间才能找到小K

一行一个整数  表示时间

4 3
1 2 1
2 3 1
3 4 1

4

$3$ $\le$ $N$ $\le$ $200,000$ $1$ $\le$ $ui$, $vi$ $\le$ $N$，$1$ $\le$ $ci$ $\le$ $1,000,000,000$