大逃离

题目背景

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 \leq n,w \leq 10000$）

输出格式

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

提示

对于 $50\%$ 的数据：$n \leq 10,m \leq 10$。

对于 $90\%$ 的数据：$n \leq 1000,m \leq 20000$。

对于 $100\%$ 的数据：$n \leq 5000,m \leq 100000$。

另外，$k$ 比较小。

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