贝西搬到了一个小农场，有时候，她会回来看看她的朋友们。由于路上风景不错，她不想走得太快于是贝西决定不走最短路径，而是走次短（即第二短）的路径（假定次短路径一定是存在的）。
    村里一共有R (1 ≤ R ≤ 100000)条双向道路，N (1 ≤ N ≤ 5000)个结点（从1到N编号）。
    贝西的起点是1号点，目的地（就是她朋友的家）在N号点。
    次短路径的有些边可以和最短路径重复，而且也允许存在圈，即次短路径上允许重复多次通过一些点或边。我们要求次短路径要严格大于最短路径。比如说，如果有两条不同的路径都是最短路径，那么他们都不能算是次短路径，次短路径一定要比它们长。

第一行：两个用空格分开的整数：N和R
第二行到R + 1行：每一行有三个整数：A，B和D，表示一条道路连接了A点和B点，长度为D (1 ≤ D ≤ 5000)

单独一行：从1号点到N号点的第二短的路径。

4 4 
1 2 100 
2 4 200 
2 3 250 
3 4 100

450