题目背景

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

题目描述

这是一张有 $n$ 个节点，$m$ 条双向边的图，每一条边有 $w$ 个单位距离，zrz 在 $1$ 的位置，出口在 $n$ 的位置。

不过 zrz 脑子出了点 bug，不想走最短的路，想走第二短的路。第二短路径允许与最短路径有重边，也可以重复通过一些节点和边。注意，如果有多条路径都是最短路径，那么他们都不能叫第二短路径。

另外，如果接下来进入的一个节点，它所直接连接的地方小于 $k$ 个（起点和终点除外），那么 zrz 就会不敢进去。

输入格式

第一行三个数：$n,m,k$。

接下来 $m$ 行，每行三个数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条权值为 $w$ 的双向边。

输出格式

一个数，表示从 $1$ 走到 $n$ 的第二短路的值，如果不存在，输出 $-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 \leq 10$，$m \leq 10$；

对于 $90\%$ 的数据：$n \leq 1000$，$m \leq 20000$；

对于 $100\%$ 的数据：$1\leq n \leq 5000$，$1\leq m \leq 100000$，$1\leq u,v \leq n$，$1\leq w\leq 10000$。

另外，$k$ 比较小。

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