Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Policija

Šiame uždavinyje Maksimas ir Linas tęsia savo kelionę (taip, istorija prasidėjo kitame uždavinyje). Iš taško B jiems reikia nuvykti į tašką C. Kaip ir visuomet, Maksimas nori važiuoti trumpiausiu keliu. Negalime atskleisti visų detalių, tačiau šios kelionės metu jiedviems reikia išvengti policijos.

Parašykite programą, kuri rastų trumpiausią įmanomą kelią iš taško B į tašką C, tokį, kuriame nepasitaikytų policija, arba nustatytų, kad tokio kelio nėra.

Pradiniai duomenys

Pirmoje eilutėje pateikti penki sveikieji skaičiai: N, B, C, G ir P. N yra sankryžų skaičius (N\\le1000), visos sankryžos sunumeruotos skaičiais nuo 1 iki N. B ir C - tai sankryžų, kuriose kelionę pradės ir baigs mūsų keliautojai, numeriai. G yra gatvių, o P - policijos ekipažų 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, po vieną eilutėje, faile įrašyta P sankryžų numerių, kuriose budi policijos ekipažai. Tarp šių sankryžų numerių nėra B ir C.

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 B, baigtis numeriu C. Šioje sekoje neturi būti sankryžų, kuriose budi policijos ekipažai.

Jei yra keli sprendiniai, programa gali pateikti bet kurį iš jų. Jei "saugaus" kelio nėra, programa į pirmą rezultato failo eilutę turi įrašyti -1.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6 1 6 8 2
1 2 500
1 3 300
1 4 200
2 5 800
2 6 1500
3 5 300
4 5 300
5 6 300
3
4
 
1600
1 2 5 6
 
7 1 7 9 2
1 2 1300
1 3 1000
2 4 900
2 5 550
3 4 1100
3 5 1200
4 6 860
5 7 1420
6 7 1170
4
5
 
-1