Benzinas

Pradinių duomenų failas:

benzinas.in  

Rezultatų failas:

benzinas.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

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ų failo eilutėje įrašyti penki sveikieji skaičiai: N, A, B, G ir K. N yra sankryžų skaičius (N <= 1000), 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ų (l <= 5000). Gatvės yra dviejų pusių eismo; dvi sankryžas jungia ne daugiau negu viena gatvė.

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

Rezultatai

Rezultatus programa turi įrašyti į rezultatų failą. 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

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