小葱去里约看奥运会,早上从酒店出来后决定坐公交车吗,但是没有直达的路线,只能通过多次换乘公交来达到目的地,现在希望你可以编写一个程序帮助小葱算数到达目的地所需的最少时间
输入描述:
第一行的第一个数字表示终点,起点用数字0表示,第二个数字N表示可选的巴士路线(1≤N≤100).第二行开始表示巴士的线路,第一个数字是起点,第二个数字表示这条巴士线路的终点,第三个数字表示这条线路需要的时间


输出描述:
输出一行表示最少时间,如果到不了则输出-1。
示例1

输入

6 5
0 2 5
1 4 3
2 6 4
4 6 1
2 4 3

输出

9
加载中...