T3 免费通行（road）

题目描述

小真得到了一张城际通行优惠卡：从城市 $1$ 前往城市 $n$ 的途中，最多可以选择 $k$ 条道路免费通行（其余道路仍需支付通行费）。

地图上共有 $n$ 个城市、$m$ 条双向道路，第 $i$ 条道路连接城市 $u_i,v_i$，通行费为 $w_i$。

请帮小真求出从城市 $1$ 到城市 $n$ 的最小总通行费。若无法到达，输出 -1。

输入文件 road.in，输出文件 road.out。

输入格式

第一行三个整数 $n,m,k$，分别表示城市数、道路数与免费通行的最大次数。

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

输出格式

输出共一行一个整数，表示最小总通行费；若无法到达，输出 -1。

样例 1 输入

4 5 1
1 2 10
2 4 10
1 3 5
3 4 5
2 3 1

样例 1 输出

5

样例 1 解释

小真走 $1 \to 3 \to 4$，并对道路 $3 \to 4$ 使用一次免费通行，总费用为 $5+0=5$。

样例 2 输入

3 2 0
1 2 10
2 3 20

样例 2 输出

30

样例 3 输入

4 2 1
1 2 10
3 4 5

样例 3 输出

-1

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 10,m \le 12$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$0 \le m \le 2\times 10^5$，$0 \le k \le 10$，$1 \le u_i,v_i \le n$，$1 \le w_i \le 10^9$。