Description

克里斯再次逃学去朋友家里玩了，生气的克里斯的父母决定把他给捉回来。

他的父母深知克里斯一定是在夏尔米或者七枷社家里玩。

克里斯所在的城市由 $N$ 个居住点和 $M$ 条连接居住点的双向街道组成，经过街道 $x$ 需要花费 $T_x$ 分钟。

可以保证，任意两个居住点之间有且仅有一条通路。

克里斯家在点 $C$，夏尔米和七枷社家分别在点 $A$ 和点 $B$。

为了尽快找到克里斯，他的父母在寻找他时将遵守如下两条规则：

如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，则他的父母先到夏尔米家去找他，如果找不到，再去七枷社家。反之亦然。 克里斯的父母总沿着两点间唯一的通路行走。 但是我们并不知道 $A、B、C$ 三个点的具体位置。

请你计算在最坏的情况下，克里斯的父母要花多久才能找到他？

Input Format

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含三个整数 $u，v，t$，表示居住点 $u$ 和居住点 $v$ 之间存在一条街道，且经过该街道需要花费 $t$ 分钟。

街道信息不会重复给出。

Output Format

输出一个整数，表示克里斯父母在最坏的情况下，找到他需要花费的分钟数。

4 3
1 2 1
2 3 1
3 4 1

4

Hint

数据范围 $3 \le N \le 200000$, $M=N-1$, $1 \le u,v \le N$, $1 \le t \le 1000000000$