Šeštadieninė informatikos olimpiadininkų mokykla

Nedideliame mieste kompanijos "Oro uosto ekspresas" autobusai nuveža keleivius į oro uostą daug greičiau nei kitos transporto priemonės. Yra dviejų klasių reisai: ekonominės ir komercinės. Jie važiuoja skirtingais greičiais, maršrutais, kainuoja skirtingai.

Jonas keliauja į oro uostą pasitikti draugo. Jis norėtų keliauti komercinės klasės autobusu, bet neturi pakankamai pinigų. Tačiau, jis turi bilietą, su kuriuo jis gali pavažiuoti komercinės klasės autobusu vienu sustojimu pirmyn. Sumaniai panaudojęs bilietą, jis galėtų sutaupyti daug laiko. Tačiau jam nėra lengva pasirinkti tinkamą momentą, kada panaudoti tą bilietą.

Padėkite Jonui ir parašykite programą, kuri rastų, kaip greičiausiai Jonas gali pasiekti oro uostą.

Pradiniai duomenys

Pirmoje eilutėje yra trys sveiki skaičiai N, S ir E (, ). Tai yra, atitinkamai, stotelių kiekis, pradinės stotelės numeris ir oro uosto (galinės) stotelės numeris.

Kitoje eilutėje yra vienas sveikas skaičius M () - ekonominės klasės autobusų reisų kiekis. Kiekvienoje iš tolesnių M eilučių yra po tris sveikus skaičius X, Y ir Z (, ), kurie reiškia, kad yra maršrutas jungiantis stoteles X ir Y, trunkantis Z minučių.

Kitoje eilutėje yra sveikas skaičius K () - komercinės klasės autobusų reisų kiekis. Tolesnėse K yra aprašyti komercinės klasės reisai tokiu pačiu formatu, kaip ir ekonominės.

Visi reisai yra dvikrypčiai. Galite laikyti, kad egzistuoja vienintelis optimalus maršrutas iki oro uosto. Taip pat laikykite, kad Jonui nereikia laukti stotelėse.

Rezultatai

Pirmoje eilutėje surašykite visas stoteles, kurias Jonas aplankys, jų aplankymo tvarka. Stotelių numerius atskirkite vienu tarpu.

Antroje eilutėje parašykite numerį stotelės, kurioje Jonas panaudos savo bilietą. Jei bilieto panaudoti neverta, rašykite -1.

Trečioje eilutėje rašykite visos kelionės laiką, minutėmis.

Pavyzdys

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

1 2 4
2
5