题目描述

贝西在外地，想在农夫约翰叫醒她早上挤奶之前回到谷仓旧能多地睡觉。贝西需要她的美容觉，所以她想眷回来。

$\red{Farmer John }$的田地中有 $\red{N (2 <= N <= 1000) }$个地标，唯一编号为 $\red{1...N}$。

地标 $\red{1 }$是谷仓； $\red{Bessie }$整天站立的苹果树林是 $\red{N }$号地标。

奶牛在地标之间使用$\red{T (1 <= T <= 2000) }$条不同长度的双向奶牛小径在田间行进。 $\red{Bessie }$对自己的导航能力没有信心，所以一旦开始，她总是会从头到尾一 直在跟踪。

给定地标之间的小径，确定$\red{Bessie }$必须步行才能返回谷仓的最小距离。保证存在一些这样的路线。

输入格式

第$\red{1 }$行：两个整数：$\red{T }$和 $\red{N }$

第$\red{2...T+1 }$行：每行将轨迹描述为三个以空格分隔的整数。前两个整数是路径经过的地标。

第三个整数是轨迹的长度，范围为$\red{1...100}$。

输出格式

第$\red{1 }$行：单个整数，$\red{Bessie }$从地标 $\red{N }$到地标 $\red{1 }$必须经过的最小距离。

样例

输入样例

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

输出样例

90

提示

输入详细信息：有五个地标。

输出详细信息：贝西可以沿着小路$\red{4}$、$\red{3}$、$\red{2}$和$\red{1}$回家。