No Crossing

Problem Description

Given a directed graph, find the shortest path that passes through exactly $k$ nodes, with the requirement that each chosen edge must not "cross" any previously visited node. That is, for an edge $x \to y$ on the path, there must be no previously visited node $t$ such that $\min(x, y) \le t \le \max(x, y)$.

Input Format

The first line contains three integers $n, k, m$.

The next $m$ lines each contain three integers $a_i, b_i, c_i$, indicating a directed edge from $a_i \to b_i$ of length $c_i$.

Output Format

One integer — the answer. If no path satisfies the condition, output $-1$.

Sample Input 1

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

Sample Output 1

6

Sample Input 2

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

Sample Output 2

3

Sample Explanation

In sample 1, the shortest path is $1 \to 6 \to 2 \to 4$. The path $1 \to 6 \to 2 \to 7$ is invalid because $2 < 6 < 7$.

Constraints

All data satisfy $1 \le n, k \le 100$, $0 \le m \le 2000$, $1 \le a_i, b_i \le n$, $1 \le c_i \le 1000$.