#300. 逃学的小孩
逃学的小孩
题目描述
克里斯再次逃学去朋友家里玩了,生气的克里斯的父母决定把他给捉回来。
他的父母深知克里斯一定是在夏尔米或者七枷社家里玩。
克里斯所在的城市由个居住点和条连接居住点的双向街道组成,经过街道需要花费分钟。
可以保证,任意两个居住点之间有且仅有一条通路。
克里斯家在点,夏尔米和七枷社家分别在点和点。
为了尽快找到克里斯,他的父母在寻找他时将遵守如下两条规则:
、如果距离比距离近,则他的父母先到夏尔米家去找他,如果找不到,再去七枷社家。反之亦然。
、克里斯的父母总沿着两点间唯一的通路行走。
但是我们并不知道三个点的具体位置。请你计算在最坏的情况下,克里斯的父母要花多久才能找到他?
输入格式
第一行包含两个整数和。
接下来行,每行包含三个整数,表示居住点和居住点之间存在一条街道,且经过该街道需要花费分钟。
街道信息不会重复给出。
输出格式
输出一个整数,表示克里斯父母在最坏的情况下,找到他需要花费的分钟数。
样例
输入样例
4 3
1 2 1
2 3 1
3 4 1
输出样例
4
提示
,
,