这是一棵有 $n$ 个节点的图，有 $m$ 条双向边，每一条路有 $w$ 个单位距离。

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

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

接下来 $m$ 行：每行三个数，$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$ 比较小。

500

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