Problem E: 小红帽拯救外婆

Problem E: 小红帽拯救外婆

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 125  Solved: 47
[Submit] [Status] [Web Board] [Creator:]

Description

众所周知,小红帽的外婆被狼吃了。小红帽想回到外婆被吃之前拯救她,唰嗖嚓,小红帽回到刚到森林的时候,她必须赶快去外婆家。但是森林里有很多路口。

Input

第一行输入两个整数T1T≤10000),N1N1000)—表示一共有N个路口(1为小红帽的位置,N为外婆的位置),T条路。

 接下来T行每行三个整数a,b,c—表示a路口到b路口所花的时间为c1c10000,双向的)。

以文本结束 



Output

对于每一个样例输出一个整数—表示最少花费的时间。

Sample Input Copy

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

Sample Output Copy

90