P15944 [JOI Final 2026] 传送机 2 / Teleporter 2

在一条直路上有 $N$ 个点，从左到右依次编号为 $1,2,\dots,N$。这条路是从左向右的单行道。 还有 $M$ 个传送设备，编号为 $1,2,\dots,M$。使用设备 $i$（$1 \leq i \leq M$），可以从点 $S_i$ 传送到点 $T_i$（$S_i < T_i$）。 Bitaro 目前在点 $1$，并希望到达点 $N$。当 Bitaro 在点 $j$（$1 \leq j \leq N-1$）时，他可以采取以下行动之一： - 步行移动到点 $j+1$。 - 选择一个满足 $S_i = j$ 的 $i$（$1 \leq i \leq M$），使用设备 $i$，并传送到点 $T_i$。 已知传送旅行会对身体造成压力。你很担心 Bitaro 的安全，因此你决定摧毁零个或多个传送设备，以便无论 Bitaro 采取哪条路线，传送旅行的次数最多为 $K$ 次。支付 $C_i$ 的代价可以摧毁设备 $i$；如果这样做，Bitaro 就不能再使用该设备。 求出你在摧毁零个或多个传送设备时所需支付的最小总代价，使得无论 Bitaro 的路线如何，传送旅行的次数最多为 $K$ 次。

从标准输入读取以下数据。 > $N$ $M$ $K$\ > $S_1$ $T_1$ $C_1$\ > $S_2$ $T_2$ $C_2$\ > $\vdots$\ > $S_M$ $T_M$ $C_M$

向标准输出写入一行，包含最小的可能总代价。

### 样例 1 考虑摧毁设备 $3$ 和 $4$ 的情况。 这样 Bitaro 只能使用设备 $1$ 和 $2$。当从点 $1$ 移动到点 $8$ 时，Bitaro 将始终最多进行一次传送旅行，因此条件得到满足。 在这种情况下，支付的总代价为 $4$。由于不可能使代价最多为 $3$，因此正确的输出是 $4$。 这个输入样例满足所有子任务的约束条件。 ### 样例 2 摧毁设备 $2$ 和 $5$ 是最优的。 这个输入样例满足子任务 $2,3,4,5,6$ 的约束条件。 ### 样例 3 在这种情况下，不需要摧毁任何设备。 这个输入样例满足子任务 $2,3,4,5,6$ 的约束条件。 ### 约束条件 - $2 \leq N \leq 100000$。 - $1 \leq K \leq M \leq 100000$。 - $1 \leq S_i < T_i \leq N$ ($1 \leq i \leq M$)。 - $1 \leq C_i \leq 10^9$ ($1 \leq i \leq M$)。 - 给定的值均为整数。 ### 子任务 1. (5 分) $K = 1$。 2. (3 分) $N \leq 20$, $M \leq 20$。 3. (29 分) $N \leq 500$, $M \leq 500$。 4. (23 分) $N \leq 4000$, $M \leq 4000$。 5. (24 分) $N \leq 40000$, $M \leq 40000$。 6. (16 分) 无附加限制。