题目描述

给定一张 $n$ 个点 $m$ 条边的带权有向图，第 $i$ 条边从 $u_i$ 指向 $v_i$，边权为 $w_i$，你可以翻转至多 $k$ 条边的方向，求从 $1$ 到 $n$ 的最短路，如果无法到达，输出 $-1$。

输入格式

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

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$ ，表示一条边。

输出格式

一行一个整数，表示你的答案。

2 1 1
2 1 1

1

数据范围

$$\begin{aligned} & \bullet \ 2 \le n \le 10^5\\ & \bullet \ 0 \le m \le 2 \times 10^5\\ & \bullet \ 1 \le u_i,v_i \le n\\ & \bullet \ 0 \le k \le 10\\ & \bullet \ 0 \le w_i \le 10^9 \\ & \bullet 不含重边和自环 \end{aligned}$$