z-pumpe

Drzava Zetix ima N (1 <= N <= 100) gradova. Od cega M (0 < M <= N) gradova ima pumpe. Izmedju svaka dva grada postoji najvise jedan direktan put. Prijatelji malo Z-a, Mister D i Mister S, vole da se voze i danas su resili da idu od grada 1 do grada N. Oni znaju da u njihov rezervoar moze da stane L (1 < L <= 10 000 000) litara goriva. Izmedju svaka dva grada znaju koliko goriva mu je potrebno. Gorivo mogu da sipaju u bilo kom gradu koji ima pumpu. <br><br>

Oni traz od malog Z-a pomoc, a pita Vas pita (jer ne moze sam da izracuna) koliko je najmanje potrebno goriva da bi stigao iz grada 1 u grad N. U gradu 1 ima pun rezeorvar, ali moze dopuniti rezeorvar u nekom od gradova koji imaju pumpu, naravno ako prolazi kroz taj grad.<br><br>

Ulaz:<br><br>
U prvom redu se ucitavaju redom brojevi N, M, L i K. Broj K (0 < K <= N^2) predstavlja broj puteva koji povezuju neka dva grada.
Od 2-og do K+1-og reda se u i+1-om redu ucitavaju brojevi a, b, w. Brojevi a i b su gradovi koji su spojeni putem za koji je potrebno w (1 <= w <= 10 000 000) litara goriva (putevi su dvosmerni).
Od K+2-og do M+K+1-og reda se u redu i+K+1 ucitava broj i-ti grad koji ima pumpu.<br><br>

Izlaz:<br><br>
Na standardni izlaz treba ispisati jedan broj koji predstavlja najmanju kolicinu goriva koja je potrebna da se stigne od grada 1 do grada N. Ako je nemoguce stici (ili ce nestati goriva na putu ili nema puta koji vodi od 1 do N) onda ispisati –1.<br><br>

Primer:<br><br>


Ulaz:<br>
4 1 5 4<br>
1 2 5<br>
2 4 5<br>
1 3 3<br>
3 4 3<br>
2<br><br>

Izlaz:<br>
10<br>