2672 - 单源次短路
时间限制 : 1 秒
内存限制 : 128 MB
给定一个1~n个节点编号的图，求从起点为1，终点为n的，不重复经过边的，仅次于最短路的次短路径。
输入
第一行包含2个整数n，m,分别表示图的节点编号数和边的数量。
接着m行，每行包含3个整数u,v,w，表示u和v之间有条单向边，边的权值为w。
输出
输出仅一个数，即次小权值。
如果没有最短路或者最小权值，输出-1
样例
输入
4 6 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出
4
输入
5 6 1 2 1 2 3 1 3 5 1 3 2 1 1 4 10 4 5 10
输出
20
提示
2 \leq n \leq 10^3, 2 \leq m \leq 10^5 ，0 < w \leq 10^5
来源
模板