给出一个有向图，找一条恰好经过 $k$ 个点的最短路径，要求每次选的边不能跃过之前已经经过的节点。即对于路径中的边 $x \rightarrow y$ ,不存在以前经过的点 $t$ 使得三者的编号满足 $min(x,y) \leq t \leq max(x,y)$ 。

输入格式

第一行三个数字 $n,k,m$。

接下来$m$行 , 每行 $3$ 个整数 $a_i,b_i,c_i$表示存在一条从 $a_i \rightarrow b_i$ , 长度为 $c_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

数据规模

所有数据保证 $1\leq n,k\leq 100, 0 \leq m \leq 2000 , 1 \leq a_i,b_i \leq n , 1 \leq c_i \leq 1000 ,$。

Note

样例一的最短路径为 $1 \rightarrow 6 \rightarrow 2 \rightarrow 4$ 。 $1 \rightarrow 6 \rightarrow 2 \rightarrow 7$是不正确的，因为 $2 < 6 < 7$。