CF793D.Presents in Bankopolis

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.

Bankopolis 是一座不可思议的城市，其中所有 $n$ 个十字路口都位于一条直线上，并沿该直线从 $1$ 到 $n$ 编号。每个十字路口处均设有一家银行办事处。

这些十字路口之间由 $m$ 条有向自行车道相连（第 $i$ 条车道从十字路口 $u_i$ 指向十字路口 $v_i$），每条车道的难度已知。

银行客户奥列格希望为银行员工带来幸福与喜悦，他计划恰好访问 $k$ 家办事处，并在每家办事处向员工赠送礼物。

但问题在于：奥列格不愿目睹员工收到礼物时的反应，因此他不能使用任何经过他已赠送过礼物的办事处所在十字路口的自行车道（形式化定义：第 $i$ 条车道经过第 $x$ 号十字路口处的办事处，当且仅当 $\min(u_i,\,v_i) < x < \max(u_i,\,v_i)$）。当然，奥列格在每家办事处仅能赠送一次礼物。他将恰好使用 $k-1$ 条自行车道在各办事处之间移动。奥列格可从任意一家办事处出发，亦可在任意一家办事处结束行程。

奥列格希望在所有可行路径中，选出总难度最小的一条路径。请找出这一最小可能的总难度。

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.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 80$）——分别为路口（同时也是办公地点）的数量，以及 Oleg 想要访问的办公地点数量。

第二行包含一个整数 $m$（$0 \leq m \leq 2000$）——表示 Bankopolis 市自行车道的数量。

接下来的 $m$ 行描述这些自行车道的信息。

其中第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \leq u_i, v_i \leq n$，$1 \leq c_i \leq 1000$），分别表示第 $i$ 条道路所连接的两个路口及其难度。

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.

在唯一一行中输出有效路径中各车道的最小可能总难度；如果不存在有效路径，则输出 $-1$。

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.

在第一个例子中，奥列格按照路径 $1 \rightarrow 6 \rightarrow 2 \rightarrow 4$ 访问银行。

路径 $1 \rightarrow 6 \rightarrow 2 \rightarrow 7$ 虽然难度更小，但不合法，因为岔路口 $2 \rightarrow 7$ 经过已访问过的、位于岔路口 $6$ 的银行办公室。

在第二个例子中，奥列格可以按照路径 $4 \rightarrow 1 \rightarrow 3$ 访问银行。