Description
PIPI的家乡出现了灾害！！！
现在地图上有n个城镇，编号为1~n，PIPI的家乡恰好为n城镇，PIPI要赶去送物资，PIPI现在位于1号城镇
但是PIPI发现，他不知道去往其他城镇的路，于是他只好向附近的人打听
经过一番努力，PIPI打听到了m条消息，对于每一条消息，PIPI可以提炼出一条从s城镇直达t城镇的路，以及花销c，
但是由于不同的人所走的线路不同，所以从s城镇到t城镇可能会有很多条直达道路（对于每一条道路，往返的花销相同）
PIPI现在很着急，他想知道如何用最小的花销到达自己家乡n，你能帮帮他吗？
Input
第一行两个整数n和m，表示城镇数和PIPI打听到的消息数
接下来m行，每一行有三个数，s，t，c表示从s城镇到t城镇有一条路，花销为c
1 <= n <= 5000, 1 <= m <= 500000, 1 <= c <= 1000
Output
输出一个数表示PIPI到达家乡的最小花销
如果从m条消息中PIPI无法获知到达家乡的路，则输出-1
Sample Input
7 11
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1