延空木到电波塔有很长的一段距离，并且由于种种原因，原本笔直的道路变得支离破碎。但护妻心切的takina不管这么多，她手上有着这一带的地图网络，现在需要你找出，从延空木到电波塔的最短距离.
第一行为两个整数n m,表示总共有n个地点,m条道路
接下来有m行，每行有三个整数a b c，代表地点a和地点b之间有着需要c分钟才能走过的道路
注意：延空木编号为1，电波塔编号为n。takina并不需要走遍所有地点，毕竟她是去救人不是去逛街。同时所有道路都是双向的，即你可以从a到b，也可以从b到a
输入1：
5 5
1 2 1
2 3 1
3 4 1
1 5 4
5 4 2
输入2：
9 12
1 2 1
2 3 2
3 4 6
2 5 7
4 5 1
4 6 3
5 8 2
6 8 55
1 7 10
5 7 1
8 9 1
7 9 1141514
3 2
1 2 1
2 3 2
3