Hay \(n\) ciudades, numeradas de \(0\) a \(n - 1\), y \(m\) vuelos dirigidos, cada uno con su precio. Encuentra el precio más bajo para ir de la ciudad \(s\) a la \(t\) haciendo a lo más \(k\) escalas (es decir, usando a lo más \(k + 1\) vuelos). Si no se puede, la respuesta es \(-1\).

Entrada

La primera línea tiene \(n\) \((2 \le n \le 100)\), \(m\) \((1 \le m \le n(n-1)/2)\), \(s\), \(t\) \((s \ne t)\) y \(k\) \((0 \le k < n)\). Cada una de las siguientes \(m\) líneas tiene un vuelo \(u\) \(v\) \(p\) \((u \ne v, 1 \le p \le 10^4)\). No hay vuelos repetidos.

Salida

El precio más bajo, o \(-1\).

Ejemplo 1

Entrada

4 5 0 3 1
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200

Salida

700

Ejemplo 2

Entrada

3 3 0 2 1
0 1 100
1 2 100
0 2 500

Salida

200

Ejemplo 3

Entrada

3 3 0 2 0
0 1 100
1 2 100
0 2 500

Salida

500