题目描述

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

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

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

可以保证，任意两个居住点之间有且仅有一条通路（即城市结构是一棵树）。

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

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

1. 如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，则他的父母先到夏尔米家去找他，如果找不到，再去七枷社家。反之亦然。
2. 克里斯的父母总沿着两点间唯一的通路行走。

但是我们并不知道 $A$、$B$、$C$ 三个点的具体位置。

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

输入格式

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

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

街道信息不会重复给出。

输出格式

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

样例

输入样例：

4 3
1 2 1
2 3 1
3 4 1

输出样例：

4

样例解释

城市结构如下：

1 - 2 - 3 - 4

每条边花费时间为 1。

最坏情况：$A = 1$, $B = 4$, $C = 3$。

此时：

• $A$ 到 $C$ 的距离为 2
• $B$ 到 $C$ 的距离为 1

由于 $B$ 距离 $C$ 更近，父母先去七枷社家（$B=4$），花费 1 分钟，没找到。 然后去夏尔米家（$A=1$），需要从 $C=3$ 走到 $A=1$，花费 2 分钟。 但从 $4$ 到 $1$ 需要经过 $3$，实际路线是：$3 \to 4$（已走过）$\to 3 \to 2 \to 1$，总花费为 $1 + 3 = 4$ 分钟。

数据范围

• $3 \leq N \leq 2 \times 10^5$
• $M = N - 1$
• $1 \leq u, v \leq N$
• $1 \leq t \leq 10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB