题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

街道信息不会重复给出。

输出格式

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

样例

输入样例

4 3
1 2 1
2 3 1
3 4 1

输出样例

4

提示

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

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

$\red {1≤t≤1000000000}$