题目背景

zrz走进了一个奇葩的迷宫，他发现自己迷路了，想逃出来，他好不容易数完了所有的路，累的快晕了，只好叫你帮忙咯。

题目描述

这是一棵有n个节点的图，有m条双向边，每一条路有w个单位距离，zrz在1的位置，出口在n的位置，不过zrz脑子出了点bug，于是不想走最短的路，想走第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

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

450

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

500

提示

对于50%的数据：n<=10,m<=10

对于90%的数据：n<=1000,m<=20000

对于100%的数据：n<=5000，m<=100000

另外，k比较小

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