Eprusia es una ciudad increíble en la que todos los n cruces se encuentran en una línea recta y numerados de ~1~ a ~n~ a lo largo de ella. En cada cruce hay una oficina de banco.

Los cruces están conectadas con ~m~ carriles de bicicleta orientados (el \(i-ésimo\) carril va desde el cruce ~u_i~ hasta el cruce ~v_i~), se conoce la dificultad de cada uno de los carriles.

Marcos el cliente del banco quiere regalar felicidad y alegría a los empleados del banco. Él quiere visitar exactamente ~k~ oficinas, y en cada una de ellas quiere regalar regalos a los empleados.

El problema es que Marcos no quiere ver la reacción de sus obsequios, por lo que no puede utilizar un carril que pasa cerca de la oficina en la que ya ha presentado sus regalos (formalmente, el ~i-th~ carril pasa cerca de la oficina en el cruce \(x-ésimo\) si y sólo si ~min (u_i , v_i) < x < max (u_i , v_i)~. Por supuesto, en cada una de las oficinas Marcos puede presentar regalos exactamente una vez. Marcos va a usar exactamente ~k-1~ carriles para moverse entre las oficinas. Marcos puede comenzar su camino desde cualquier oficina y terminarla en cualquier oficina.

Marcos quiere seleccionar el camino entre todos los posibles que la dificultad total de los carriles que utilizará es el mínimo posible. Encuentra esta dificultad mínima posible.

Entrada

La primera línea contiene dos números enteros ~n~ y ~k~ ~(1 \leq n, k \leq 80)~ - el número de cruces (y oficinas) y el número de oficinas que Marcos quiere visitar.

La segunda línea contiene un entero ~m~ ~(0 \leq m \leq 2000)~ - el número de carriles para bicicletas en Eprusia.

Las siguientes ~m~ líneas contienen información sobre los carriles.

El \(i-ésimo\) de estas líneas contiene tres enteros ~u_i~, ~v_i~ y ~c_i~ ~(1 \leq u_i, v_i \leq n, 1 \leq c_i \leq 1000)~, que denotan el cruce conectado por la \(i-ésima\) carretera y su dificultad.

Salida

En la única línea imprime la dificultad total mínima posible de los carriles en una ruta válida, o -1 si no hay rutas válidas.

Ejemplo de Entrada 1

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

Ejemplo de Salida 1

6

Ejemplo de Entrada 2

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

Ejemplo de Salida 2

3

Explicación

En el primer ejemplo las oficinas visitadas por Marcos describen el camino ~1~ → ~6~ → ~2~ → ~4~.

El camino ~1~ → ~6~ → ~2~ → ~7~ con menor dificultad es incorrecto porque el cruce ~2~ → ~7~ pasa cerca de la oficina ya visitada en el cruce ~6~.

En el segundo ejemplo, Marcos puede visitar los bancos por el camino ~4~ → ~1~ → ~3~.