← 返回题目列表

Codeforces · 793/D

D. 在 Bankopolis 呈现

中文机器翻译题面 查看原题

Bankopolis 是一座令人难以置信的城市,其中所有 n 个十字路口都位于一条直线上,并沿直线编号为 1 到 n。每个十字路口都有一家银行办事处。

十字路口连接着m条向自行车道(第i条车道从十字路口ui到十字路口vi),每条车道的难度都是已知的。

银行客户奥列格希望为银行员工带来幸福和快乐。他想参观恰好 k 个办公室,在每个办公室里他都想给员工赠送礼物。

问题是 Oleg 不想看到人们对他的礼物的反应,因此他不能使用经过他已经赠送礼物的办公室附近的自行车道(正式来说,第 i 条车道经过第 x 个十字路口的办公室附近当且仅当 min(ui, vi) < x < max(ui, vi))。当然,奥列格在每个办公室只能赠送一次礼物。 Oleg 将使用 k-1 条自行车道在办公室之间移动。奥列格可以从任何办公室开始他的道路并在任何办公室完成它。

Oleg 希望在可能的路径中选择这样一条路径,使得他将使用的车道的总难度尽可能最小。求这个最小可能的总难度。

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 80) - 十字路口(和办公室)的数量以及 Oleg 想要访问的办公室的数量。

第二行包含单个整数 m (0 ≤ m ≤ 2000) — Bankopolis 的自行车道数量。

接下来的 m 行包含有关车道的信息。

其中第 i 行包含三个整数 ui、vi 和 ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 1000),表示第 i 条路连接的十字路口及其难度。

输出

在唯一的行中打印有效路径中车道的最小可能总难度,如果没有有效路径,则打印 -1。

示例

输入 #1

7 4
4
1 6 2
6 2 2
2 4 2
2 7 1

输出 #1

6

输入 #2

4 3
4
2 1 2
1 3 2
3 4 2
4 1 1

输出 #2

3

注意

在第一个示例中,Oleg 通过路径 1 → 6 → 2 → 4 访问银行。

难度较小的路径 1 → 6 → 2 → 7 不正确,因为十字路口 2 → 7 经过十字路口 6 上已访问过的办公室附近。

在第二个示例中,Oleg 可以通过路径 4 → 1 → 3 访问银行。