A21259.大逃离

这是一棵有n个节点的图，有m条双向边，每一条路有w个单位距离，zrz在1的位置，出口在n的位置，zrz想走第2短的路，第2短路径允许与最短路径有重边，然后也可以重复通过一些节点和路，注意如果有多条路径都是最短路径，那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个（起点和终点除外），那么他就不敢进去。

第一行3个数：n,m,k

接下来m行：每行3个数，u，v，w。表示从u到v有一条权值为w的边。（u,v<=n，w<=10000）

一个数：表示从s走到t的第2短路的值，如果不存在，输出-1

n<=5000，m<=100000

另外，k比较小

样例2最短路径是300（1-2-4）。因为从2无法走到3（3连接到的节点只有2个），所以可以1-2-1-2-4，第二短路为500。