3638. [NOI 2003]逃学的小孩

【题目描述】

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

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

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

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

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

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

如果 $A$ 距离 $C$ 比 $B$ 距离 $C$ 近，则他的父母先到夏尔米家去找他，如果找不到，再去七枷社家。反之亦然。

克里斯的父母总沿着两点间唯一的通路行走。

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

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

【输入格式】

第一行包含两个整数 $n$ 和 $m$。

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

街道信息不会重复给出。

【输出格式】

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

【样例输入】

4 3
1 2 1
2 3 1
3 4 1

【样例输出】

4

【数据规模与约定】

$3\leq N\leq 200000,M=N-1,1\leq u,v\leq N,1\leq t\leq 10^9$