题目描述

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

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

克里斯所在的城市由 $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

数据范围

$3≤N≤200000, M=N−1,1≤u,v≤N,1≤t≤1000000000$

来源

• NOI2003
• BZOJ1509
• 算法竞赛进阶指南