Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecţionale de transport de tipul (x, y, t) care îţi permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t secunde. Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă x pe orice altă planetă y în P secunde cu condiţia că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport. Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de K ori. Marian se află pe planeta 1 și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta N.

Cerinţă

Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Date de intrare

Prima linie a fișierului ateleport.in va conţine 5 valori N, M, P, L, K, separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe fiecare din următoarele M linii se vor afla câte 3 valori $X_i, Y_i, T_i$ care descriu un canal de transport.

Date de ieşire

Fișierul de ieșire ateleport.out va conţine o singură valoare pe prima linie care reprezintă timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Restricţii și precizări

• 1 ≤ N, M ≤ 10 000;
• 0 ≤ L, K ≤ 10;
• 1 ≤ Ti, P ≤ 100 000;
• 1 ≤ Xi, Yi ≤ N;
• între oricare două planete există cel mult un canal;
• pentru teste în valoare de 30 de puncte se garantează că K = 0 și toate canalele de comunicare au $T_i = 1$;
• pentru ALTE teste în valoare de 20 de puncte se garantează că K = 0;
• pentru ALTE teste în valoare de 20 de puncte se garantează că N ≤ 300;
• se garantează că pentru toate testele există soluţie;
• se acordă 10 puncte din oficiu.

Exemple

ateleport.in

6 7 3 2 1 
1 2 2 
1 3 5 
2 3 4 
2 4 23 
3 4 6 
5 4 7 
5 6 9

ateleport.out

14

ateleport.in

6 7 3 2 0 
1 2 2 
1 3 5 
2 3 4 
2 4 23 
3 4 6
5 4 7 
5 6 9

ateleport.out

27

Explicații

Pentru primul test:
Dispozitivul se poate folosi cel mult o dată. Pentru a ajunge pe planeta 6 în timp minim vom parcurge canalul 1 → 2 apoi ne vom teleporta până pe planeta 5 de unde vom mai parcurge canalul 5 → 6. Costul final este 2 + 3(teleportare) + 9 = 14

Pentru al doilea test:
Dispozitivul nu se poate folosi deloc. Pentru a ajunge pe planeta 6 de pe planeta 1 în timp minim, se vor parcurge canalele în ordinea 1→3→4→5→6 și se obține timpul 5+6+7+9=27 de secunde.