题目背景

为了根除系统底层的隐患，王老师需要将纯净的杀毒程序传输到核心区域。

题目描述

王老师需要从节点 1 将杀毒程序传输到节点 $N$。网络可以抽象为一个有向图，有 $M$ 条边，每条边传输耗时 $W_i$。为了加速传输，王老师可以使用他的“黑客特权”，将图中最多 $K$ 条边的耗时直接变为 0。求到达节点 $N$ 的最短总耗时。如果无法到达，输出 -1。

输入格式

第一行三个整数 $N, M, K$。 接下来 $M$ 行，每行三个整数 $u, v, w$，表示存在一条从 $u$ 到 $v$，耗时为 $w$ 的有向边。

输出格式

一个整数，表示最短总耗时。

样例输入

4 5 1
1 2 5
2 3 5
3 4 5
1 3 8
2 4 8

样例输出

5

样例解释

走 1 -> 3 -> 4 路径，将 1 -> 3 的耗时 8 变为 0，总耗时 0 + 5 = 5。

数据规模与约定

对于 100% 的数据，$1 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$0 \le K \le 20$，$1 \le w \le 10^6$。