Has venido a una estación de esquí con tus amigos para esquiar. En la estación de esquí, hay puntos intermedios establecidos a ciertas altitudes. Hay un total de $N$ puntos intermedios, numerados del 1 al $N$ en orden decreciente de altitud. Es decir, el punto más alto es el punto 1 y el punto más bajo es el punto $N$.

Actualmente, te encuentras en el punto $S$ con tus amigos. Tus amigos han acordado esquiar libremente por su cuenta y luego reunirse en el punto $T$ al finalizar.

En la estación de esquí hay $M$ pistas. Cada pista va desde el punto $a_i$ hacia el punto $b_i$, y al ingresar a ella se puede esquiar durante un tiempo $t_i$. Las pistas siempre van en la dirección en que disminuye la altitud. Es decir, se cumple que $a_i < b_i$.

Además, cada pista cuenta con un telesilla. El telesilla va en la dirección opuesta a la pista, es decir, en la dirección en que aumenta la altitud. En otras palabras, al subir al telesilla, puedes moverte desde el punto $b_i$ al punto $a_i$. Puedes subir al telesilla un máximo de $K$ veces.

Quieres llegar al punto $T$ utilizando únicamente las pistas de esquí y los telesillas, de manera que maximices el tiempo total que pasas esquiando. El tiempo que pasas en el telesilla no se incluye en el tiempo de esquí. Dada la información de las pistas, determina el tiempo máximo que puedes esquiar.

Entrada

La primera línea contiene cinco enteros $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

A continuación, se presentan $M$ líneas, cada una con la información de una pista representada por tres enteros $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$).

Hay a lo sumo una pista que conecta directamente dos puntos distintos.

Salida

Imprime un único entero que represente el tiempo máximo que puedes esquiar.

Si no es posible llegar al punto $T$ de ninguna manera utilizando las pistas y los telesillas, imprime -1 en su lugar.

Ejemplos

Entrada 1

3 2 1 1 3
1 2 10
2 3 5

Salida 1

25

Entrada 2

3 3 1 1 3
1 2 10
2 3 5
1 3 1

Salida 2

30

Entrada 3

3 2 1 3 1
1 2 10
2 3 5

Salida 3

-1

Entrada 4

3 2 2 3 1
1 2 10
2 3 5

Salida 4

0