题号：NC210729
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
新冠病毒被医生从患者的身体中赶了出来，它很伤心，原本一切都是那么的快乐，它和它的孩子们快乐地生活在一起。但是这里的抗疫力度太强了，被赶出来后，由于人们都带了口罩，它没办法再次回到之前那样的舒适环境。现在它想要离开医院回家。它有很多条路可以离开医院，虽然它想要尽可能快的回去，但是它还想看看路上的其它病毒过得怎么样，也好顺便带它们一起离开，于是它决定走第二短的路回去。医院总有 V (0 ~ V-1) 个路口，这些路口之间有 E 条路连接。新冠病毒现在在第 0 个路口，第 V-1 个路口就是医院出口。保证有路可以离开。
第二短路是严格第二短（小于最短路），保证路径存在，路径可以重复走。
输入描述:
第一行：两个空格隔开的整数 V 和 E 。( 1 <= V <= 5000 )，( 0 <= E <= 100000 ) 。
第二行开始有 E 行：每行包含 3 个空格隔开的整数 a、b、d 。表示路口 a 和 b 之间有一条长度为 d 的路。( 0 <= a,b < V )，( 0 < d <= 5000 ) 。
输出描述:
输出占一行：从路口 0 到 路口 V-1 的第二短的路径长度。
示例1
输入
复制
4 4
0 1 100
1 3 200
1 2 250
2 3 100