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 访问银行。