湖南大战在即，CDUTCM队员们都在积极准备当天的夜巡。一天傍晚，hxz对着室友说“我去训练了”便出了门。出了门他发现有好几条路线（至少一条）可以走到实验室，中间可以通过好几个路口（最少为 0），现在知道每个路口到另外一个路口需要花费的时间，那么hxz应该走哪一条才能最快到达实验室呢，请你帮帮他。
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示有几个路口，标号为1的路口是hxz的寝室所在地，标号为N的路口是实验室所在地，M则表示在中间有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的hxz需要C分钟的时间走过这条路。
输入保证至少存在1条寝室到实验室的路线。
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
3
2
最终hxz因为选择困难迟到了训练。（最短路入门——floyd）