Bankopolis is an incredible city in which all the _n_ crossroads are located on a straight line and numbered from 1 to _n_ along it. On each crossroad there is a bank office.
The crossroads are connected with _m_ oriented bicycle lanes (the _i_\-th lane goes from crossroad _u__i_ to crossroad _v__i_), the difficulty of each of the lanes is known.
Oleg the bank client wants to gift happiness and joy to the bank employees. He wants to visit exactly _k_ offices, in each of them he wants to gift presents to the employees.
The problem is that Oleg don't want to see the reaction on his gifts, so he can't use a bicycle lane which passes near the office in which he has already presented his gifts (formally, the _i_\-th lane passes near the office on the _x_\-th crossroad if and only if _min_(_u__i_, _v__i_) < _x_ < _max_(_u__i_, _v__i_))). Of course, in each of the offices Oleg can present gifts exactly once. Oleg is going to use exactly _k_ - 1 bicycle lane to move between offices. Oleg can start his path from any office and finish it in any office.
Oleg wants to choose such a path among possible ones that the total difficulty of the lanes he will use is minimum possible. Find this minimum possible total difficulty.
## Input
The first line contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 80) — the number of crossroads (and offices) and the number of offices Oleg wants to visit.
The second line contains single integer _m_ (0 ≤ _m_ ≤ 2000) — the number of bicycle lanes in Bankopolis.
The next _m_ lines contain information about the lanes.
The _i_\-th of these lines contains three integers _u__i_, _v__i_ and _c__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, 1 ≤ _c__i_ ≤ 1000), denoting the crossroads connected by the _i_\-th road and its difficulty.
## Output
In the only line print the minimum possible total difficulty of the lanes in a valid path, or _\-1_ if there are no valid paths.
[samples]
## Note
In the first example Oleg visiting banks by path 1 → 6 → 2 → 4.
Path 1 → 6 → 2 → 7 with smaller difficulity is incorrect because crossroad 2 → 7 passes near already visited office on the crossroad 6.
In the second example Oleg can visit banks by path 4 → 1 → 3.
Bankopolis 是一座奇妙的城市，所有 #cf_span[n] 个交叉口都位于一条直线上，并沿该直线从 #cf_span[1] 编号到 #cf_span[n]。每个交叉口都有一个银行办事处。
这些交叉口通过 #cf_span[m] 条有向自行车道连接（第 #cf_span[i] 条车道从交叉口 #cf_span[ui] 指向交叉口 #cf_span[vi]），每条车道的难度已知。
银行客户 Oleg 希望向银行员工赠送快乐与喜悦。他希望恰好访问 #cf_span[k] 个办事处，并在每个办事处向员工赠送礼物。
问题是，Oleg 不想看到人们收到礼物时的反应，因此他不能使用任何经过他已赠送过礼物的办事处附近的自行车道（形式上，第 #cf_span[i] 条车道经过交叉口 #cf_span[x] 附近的办事处，当且仅当 #cf_span[min(ui, vi) < x < max(ui, vi)]）。当然，每个办事处中 Oleg 只能赠送一次礼物。Oleg 将恰好使用 #cf_span[k - 1] 条自行车道在办事处之间移动。Oleg 可以从任意办事处开始路径，并在任意办事处结束。
Oleg 希望在所有可能的路径中选择一条，使得他使用的车道总难度最小。请找出这个最小可能的总难度。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 80]) —— 交叉口（和办事处）的数量以及 Oleg 想要访问的办事处数量。
第二行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m ≤ 2000]) —— Bankopolis 中自行车道的数量。
接下来的 #cf_span[m] 行包含关于车道的信息。
第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi] 和 #cf_span[ci] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[1 ≤ ci ≤ 1000])，表示第 #cf_span[i] 条道路连接的交叉口及其难度。
仅在一行中输出合法路径中车道的最小可能总难度，如果没有合法路径，则输出 _-1_。
在第一个例子中，Oleg 按路径 #cf_span[1 → 6 → 2 → 4] 访问银行。
路径 #cf_span[1 → 6 → 2 → 7] 虽然难度更小，但不合法，因为交叉口 #cf_span[2 → 7] 经过了已访问的交叉口 #cf_span[6] 附近的办事处。
在第二个例子中，Oleg 可以按路径 #cf_span[4 → 1 → 3] 访问银行。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 80]) —— 交叉口（和办事处）的数量以及 Oleg 想要访问的办事处数量。第二行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m ≤ 2000]) —— Bankopolis 中自行车道的数量。接下来的 #cf_span[m] 行包含关于车道的信息。第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi] 和 #cf_span[ci] (#cf_span[1 ≤ ui, vi ≤ n], #cf_span[1 ≤ ci ≤ 1000])，表示第 #cf_span[i] 条道路连接的交叉口及其难度。
## Output
仅在一行中输出合法路径中车道的最小可能总难度，如果没有合法路径，则输出 _-1_。
[samples]
## Note
在第一个例子中，Oleg 按路径 #cf_span[1 → 6 → 2 → 4] 访问银行。路径 #cf_span[1 → 6 → 2 → 7] 虽然难度更小，但不合法，因为交叉口 #cf_span[2 → 7] 经过了已访问的交叉口 #cf_span[6] 附近的办事处。在第二个例子中，Oleg 可以按路径 #cf_span[4 → 1 → 3] 访问银行。
**Definitions**
Let $ n, k \in \mathbb{Z} $ be the number of crossroads and the number of offices to visit, respectively.
Let $ m \in \mathbb{Z} $ be the number of directed bicycle lanes.
Let $ E = \{ (u_i, v_i, c_i) \mid i \in \{1, \dots, m\} \} $ be the set of directed edges, where $ u_i, v_i \in \{1, \dots, n\} $ and $ c_i \in \mathbb{Z}^+ $ is the difficulty.
A path is a sequence of distinct crossroads $ p = (x_1, x_2, \dots, x_k) $, with $ k $ distinct nodes, such that for each $ j \in \{1, \dots, k-1\} $, there exists an edge $ (x_j, x_{j+1}) \in E $, and **no intermediate crossroad** between $ \min(x_j, x_{j+1}) $ and $ \max(x_j, x_{j+1}) $ has been visited before (i.e., for all $ \ell \in \{1, \dots, j-1\} $, $ x_\ell \notin (\min(x_j, x_{j+1}), \max(x_j, x_{j+1})) $).
**Constraints**
1. $ 1 \leq n, k \leq 80 $
2. $ 0 \leq m \leq 2000 $
3. For each edge $ (u_i, v_i, c_i) \in E $: $ 1 \leq u_i, v_i \leq n $, $ 1 \leq c_i \leq 1000 $
**Objective**
Find the minimum total difficulty of a path of exactly $ k $ distinct crossroads satisfying the intermediate crossroad constraint, or return $-1$ if no such path exists.
Formally, minimize:
$$
\sum_{j=1}^{k-1} c_{(x_j, x_{j+1})}
$$
over all valid paths $ (x_1, \dots, x_k) $, where validity requires:
For all $ j \in \{1, \dots, k-1\} $,
- $ (x_j, x_{j+1}) \in E $, and
- $ \{x_1, \dots, x_{j-1}\} \cap \{ x \in \mathbb{Z} \mid \min(x_j, x_{j+1}) < x < \max(x_j, x_{j+1}) \} = \emptyset $.