Vous êtes venu dans une station de ski avec vos amis. Dans cette station, des points de passage sont installés à différentes altitudes. Il y a au total $N$ points de passage, numérotés de $1$ à $N$ par ordre décroissant d'altitude. Ainsi, le point $1$ est le plus élevé et le point $N$ est le plus bas.

Actuellement, vous vous trouvez au point $S$ avec vos amis. Vos amis ont convenu de se rassembler au point $T$ après avoir skié librement chacun de leur côté.

La station de ski dispose de $M$ pistes. Chaque piste relie le point $a_i$ au point $b_i$ (dans ce sens), et descendre cette piste vous permet de skier pendant une durée de $t_i$. Les pistes vont toujours dans le sens de la descente (altitude décroissante). Autrement dit, elles respectent la condition $a_i < b_i$.

De plus, chaque piste est équipée d'une remontée mécanique. La remontée mécanique fonctionne dans le sens inverse de la piste, c'est-à-dire dans le sens de la montée (altitude croissante). Ainsi, emprunter la remontée mécanique d'une piste permet de se déplacer du point $b_i$ au point $a_i$. Vous pouvez utiliser les remontées mécaniques au maximum $K$ fois au total.

Vous souhaitez rejoindre le point $T$ en utilisant uniquement les pistes de ski et les remontées mécaniques, tout en maximisant le temps total passé à skier. Le temps passé dans les remontées mécaniques n'est pas comptabilisé dans le temps de ski. Étant donné les informations sur les pistes, déterminez le temps maximum pendant lequel vous pouvez skier.

Entrée

La première ligne contient cinq entiers $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

Chacune des $M$ lignes suivantes contient trois entiers $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$) décrivant une piste.

Il y a au plus une piste reliant deux points distincts.

Sortie

Affichez un unique entier représentant le temps maximum pendant lequel vous pouvez skier.

Si, quelles que soient les pistes et remontées mécaniques choisies, il est impossible d'atteindre le point $T$, affichez -1.

Exemples

Entrée 1

3 2 1 1 3
1 2 10
2 3 5

Sortie 1

25

Entrée 2

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

Sortie 2

30

Entrée 3

3 2 1 3 1
1 2 10
2 3 5

Sortie 3

-1

Entrée 4

3 2 2 3 1
1 2 10
2 3 5

Sortie 4

0