Hay ~N~ puntos en una línea recta, numerados del ~1~ al ~N~ de izquierda a derecha. La línea es unidireccional, de izquierda a derecha. También hay ~M~ dispositivos de teletransporte, numerados del ~1~ al ~M~. Usando el dispositivo ~i~ (~1 \leq i \leq M~), se puede viajar del punto ~S_i~ al punto ~T_i~ (~S_i < T_i~).

Bitaro se encuentra actualmente en el punto ~1~ y quiere llegar al punto ~N~. Cuando Bitaro esté en el punto ~j~ (~1 \leq j \leq N-1~), puede realizar una de las siguientes acciones:

• Ir a pie al punto ~j + 1~.
• Elegir un ~i~ (~1 \leq i \leq M~) que satisfaga ~S_i = j~, usar el dispositivo ~i~ y viajar al punto ~T_i~.

Se sabe que viajar a través del espacio-tiempo generan tensión en el cuerpo. Te preocupa la seguridad de Bitaro, así que decides destruir cero o más teletransportadores para que, independientemente de la ruta que tome Bitaro, el número de viajes a través del espacio-tiempo sea como máximo ~K~. El dispositivo ~i~ se puede destruir pagando un coste ~C_i~; si se destruye, Bitaro ya no podrá usarlo.

Calcula el coste total mínimo posible que debes pagar al destruir cero o más teletransportadores para que, independientemente de la ruta de Bitaro, el número de viajes a través del espacio-tiempo sea como máximo ~K~.

Entrada

La entrada es dada en el siguiente formato:

N M K
S_1 T_1 C_1
S_2 T_2 C_2
...
S_M T_M C_M

Salida

Escribe una línea en la salida estándar con el coste total mínimo posible.

Restricciones

• ~2 \leq N \leq 100\,000~.
• ~1 \leq K \leq M \leq 100\,000~.
• ~1 \leq S_i < T_i \leq N~ (~1 \leq i \leq M~).
• ~1 \leq C_i \leq 10^9~ (~1 \leq i \leq M~).
• Todos los valores dados son enteros.

Subtareas

Subtarea	Puntos	Restricciones adicionales
~1~	~5~	~K = 1~
~2~	~3~	~N \leq 20~, ~M \leq 20~
~3~	~29~	~N \leq 500~, ~M \leq 500~
~4~	~23~	~N \leq 4000~, ~M \leq 4000~
~5~	~24~	~N \leq 40\,000~, ~M \leq 40\,000~
~6~	~16~	Sin restricciones adicionales

Ejemplos

Entrada 1

8 4 1
1 4 3
2 3 5
3 6 2
5 8 2

Salida 1

4

Considere el caso en que los teletransportadores ~3~ y ~4~ se destruyen.

Entonces Bitaro solo puede usar los teletransportadores ~1~ y ~2~. Al moverse del punto ~1~ al punto ~8~, Bitaro siempre realizará como máximo un viaje a través del espacio-tiempo, por lo que se cumple la condición.

En este caso, el costo total pagado es ~4~. Dado que es imposible que el costo sea como máximo ~3~, el resultado correcto es ~4~.

Nota: Este ejemplo de entrada satisface las restricciones de todas las subtareas.

Entrada 2

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

Salida 2

6

Destruir los teletransportadores ~2~ y ~5~ es óptimo.

Nota: Este ejemplo de entrada satisface las restricciones de las subtareas ~2, 3, 4, 5~ y ~6~.

Entrada 3

6 3 2
1 4 2
2 5 4
3 6 3

Salida 3

0

En este caso, no es necesario destruir ningún teletransportador.

Nota: Este ejemplo de entrada cumple con las restricciones de las subtareas ~2, 3, 4, 5~ y ~6~.