AT_joi2026final_f テレポーター 2 (Teleporter 2)

在一条直线上有 $N$ 个点，从左到右依次编号为 $1, 2, \ldots, N$。这条路是单向的，只能从左向右。 此外，还有 $M$ 个传送装置，编号为 $1, 2, \ldots, 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$ 个装置，从 $j$ 传送到 $T_i$ 点。 已知传送会对身体造成压力。你很担心 Bitaro 的安全，因此你决定销毁若干个（可以是零个）传送装置，使得无论 Bitaro 选择哪条路线，他的传送次数都不会超过 $K$ 次。销毁第 $i$ 个装置需要支付 $C_i$ 的花费，如果销毁该装置，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. （$5$ 分）$K=1$。 2. （$3$ 分）$N \leq 20$，$M \leq 20$。 3. （$29$ 分）$N \leq 500$，$M \leq 500$。 4. （$23$ 分）$N \leq 4\,000$，$M \leq 4\,000$。 5. （$24$ 分）$N \leq 40\,000$，$M \leq 40\,000$。 6. （$16$ 分）无其他限制。 --- ### 样例解释 1 考虑销毁第 $3$ 和第 $4$ 个装置。 那么 Bitaro 只能使用第 $1$ 和第 $2$ 个装置。此时不管怎样从 $1$ 点走到 $8$ 点，Bitaro 最多只能传送 $1$ 次，因此满足条件。 此时总花费为 $4$。由于无法使花费不超过 $3$，所以输出应为 $4$。 该输入样例满足所有子任务的限制。 --- ### 样例解释 2 销毁第 $2$ 和第 $5$ 个装置是最优的。 该输入样例满足子任务 $2,3,4,5,6$ 的限制。 --- ### 样例解释 3 此时无需销毁任何装置。 该输入样例满足子任务 $2,3,4,5,6$ 的限制。 ### 约束条件 - $2 \leq N \leq 100\,000$。 - $1 \leq K \leq M \leq 100\,000$。 - $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$）。 - 所有输入数据均为整数。 由 ChatGPT 5 翻译