题目描述

贝茜在谷仓外的农场上，她想回到谷仓，在第二天早晨农夫约翰叫她起来挤奶之前旧能多地睡上一觉．由于需要睡个好觉，贝茜必须眷回到谷仓．农夫约翰的农场上有$\red{N(2≤}$$\red{N≤}$$\red{1000)}$个路标，每一个路标都有唯一的编号（$\red{1}$到$\red{N}$）．

路标$\red{1}$是谷仓，路标$\red{N}$是贝茜一整天呆在那里的果树园．农场的所有路标之间共有$\red{T(1≤}$$\red{T≤}$$\red{2000)}$条不同长度的供奶牛走的无向小路．

贝茜对她识别方向的能力不是很自信，所以她每次总是从一条小路的头走到尾，再以这条路的尾作为下一条路的头开始走．

现给出所有路标之间的小路，要求输出贝茜回到谷仓的最短路程（每组输入数据都保证有解）．

输入格式

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

第$\red{2}$到$\red{T+1}$行：每行用空格隔开的三个整数描述一条小路．前两个整数是这条小路的尾和头，

第三个整数是这条小路的长度（不大于$\red{100}$）．

输出格式

一个整数，表示贝茜从路标$\red{N}$到路标$\red{1}$所经过的最短路程

样例

输入样例

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

输出样例

90