#300. 逃学的小孩

逃学的小孩

题目描述

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

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

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

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

克里斯家在点C\red {C},夏尔米和七枷社家分别在点A\red {A}和点B\red {B}

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

1\red {1}、如果A\red {A}距离C\red {C}B\red {B}距离C\red {C}近,则他的父母先到夏尔米家去找他,如果找不到,再去七枷社家。反之亦然。

2\red {2}、克里斯的父母总沿着两点间唯一的通路行走。

但是我们并不知道ABC\red {A、B、C}三个点的具体位置。请你计算在最坏的情况下,克里斯的父母要花多久才能找到他?

输入格式

第一行包含两个整数N\red {N}M\red {M}

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

街道信息不会重复给出。

输出格式

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

样例

输入样例

4 3
1 2 1
2 3 1
3 4 1

输出样例

4

提示

3N200000\red {3≤N≤200000},

1u,vN\red {1≤u,v≤N},

1t1000000000\red {1≤t≤1000000000}