Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Benzinas

Linas ir jo draugas Maksimas ruošiasi į kelionę. Kadangi jiedu gyvena toli vienas nuo kito, Maksimas, išvažiavęs iš taško A, ketina paimti Liną netoli jo namų, taške B. Tačiau prieš paimdamas Liną, Maksimas būtinai nori pakeliui sustoti degalinėje prisipilti benzino.

Visgi benzinas kainuoja labai brangiai, todėl Maksimas, žinodamas, jog Linas domisi algoritmais, paprašė jo rasti trumpiausią kelią iš taško A į tašką B, kuriame pasitaikytų bent viena degalinė. Padėkite Linui - parašykite programą, sprendžiančią šį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašyti penki sveikieji skaičiai: N, A, B, G ir K. N yra sankryžų skaičius (1\\leN\\le1000), visos sankryžos sunumeruotos skaičiais nuo 1 iki N. A ir B - tai sankryžų, kuriose kelionę pradės Maksimas ir Linas, numeriai. G yra gatvių, o K - benzino kolonėlių skaičius.

Sekančiose G eilučių įrašyta po tris skaičius u, v ir l, reiškiančių, jog sankryžas u ir v jungia gatvė, kurios ilgis yra l metrų (1\\leql\\le5000). Gatvės yra dviejų pusių eismo; dvi sankryžas jungia ne daugiau negu viena gatvė.

Toliau įrašyta K sankryžų numerių, kuriose yra benzino kolonėlės, po vieną eilutėje.

Rezultatai

Rezultatus programa turi įrašyti į ekraną. Jei toks kelias egzistuoja, pirmoje eilutėje turi būti įrašytas trumpiausio kelio ilgis S, o antroje - sankryžų numerių seka, apibūdinanti šį kelią. Seka turi prasidėti numeriu A, baigtis numeriu B, ir bent vienoje iš šios sekos sankryžų turi būti benzino kolonėlė.

Jei yra keli sprendiniai, programa gali pateikti bet kurį iš jų. Jei kelias neegzistuoja, programa į pirmą rezultato failo eilutę turi įrašyti -1.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
10 1 4 14 2
1 2 30
1 5 80
1 8 70
2 3 80
2 6 100
3 4 200
3 7 50
4 7 25
4 10 20
5 6 80
5 8 70
6 7 20
8 9 20
9 10 50
3
6
 
175
1 2 6 7 4