CF793D Presents in Bankopolis

Bankopolis 是一座奇妙的城市，这里的 $n$ 个十字路口都位于一条直线上，并从 $1$ 到 $n$ 依次编号。在每个十字路口都有一家银行。 十字路口之间有 $m$ 条有向自行车道，第 $i$ 条车道从十字路口 $u_i$ 通往十字路口 $v_i$，每条车道的难度已知。 银行客户 Oleg 想要为银行员工送去快乐和欢乐。他想要拜访恰好 $k$ 家银行，每到一家银行都要给那里的员工送上礼物。 问题在于，Oleg 不想看到员工收到礼物的反应，因此他不能经过靠近已经送过礼物的银行的车道（形式化地说，若 $i$ 号车道经过编号为 $x$ 的十字路口，且 $min(u_i, v_i) < x < max(u_i, v_i)$，那么只要 $x$ 已经被访问过，他就不能通过该车道）。当然，每家银行只能送一次礼物。Oleg 将恰好使用 $k-1$ 条车道在各银行之间移动，可以从任意银行开始，也可以在任意银行结束。 Oleg 想选择一条总难度最小的合规路线。请你帮忙求出最小的总难度。如果不存在合规路径，输出 $-1$。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 80$），分别表示十字路口（银行）数量和 Oleg 想要拜访的银行数。 第二行包含一个整数 $m$（$0 \leq m \leq 2000$），表示有向自行车道的数量。 接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$、$c_i$（$1 \leq u_i, v_i \leq n$，$1 \leq c_i \leq 1000$），表示一条车道起点、终点及其难度。

输出一行，表示合规路径的最小总难度。如果不存在合规路径，输出 $-1$。

在第一个样例中，Oleg 按照路径 $1 \to 6 \to 2 \to 4$ 拜访银行。 路径 $1 \to 6 \to 2 \to 7$ 的难度更小，但该路径中 $2 \to 7$ 的车道会经过已经访问过的 $6$ 号十字路口，因此不是合规路径。 在第二个样例中，Oleg 可依次拜访 $4 \to 1 \to 3$ 号银行。 由 ChatGPT 5 翻译