Description

每年，宁波大学都会举行爱心捐钱捐物活动，面对这么多爱心衣物，工作人员总是想方法降低运费，把更多的爱心送到灾区，现在他们想寻找费用最少的路线，相信热心的你一定会帮助他们的。

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示运送途中要经过的城镇数目，标号为1的是宁波大学所在地，标号为N的是灾区所在地，M则表示有几条可通的路线。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,0<=C<=1000）,表示在城镇A与城镇B之间有一条路，需要C元的金钱通过这段路。输入保证至少存在1条宁波大学到灾区的路线。

Output

对于每组输入，输出一行，表示工作人员从宁波大学到达灾区所需要的最少费用。

Sample Input

3 2
1 3 10000
2 3 20000

Sample Output

10000

HINT

Source

NBU OJ