Atommeghajtású űrhajónkkal szeretnénk eljutni egy másik csillagrendszerbe úgy, hogy a lehető legtöbb titánnal érkezzünk meg. Van egy térképünk az ismert csillagrendszerekről, melyek között kizárólag egyirányú féregjáratokon tudunk közlekedni. A féregjáratrendszer jelenlegi állapotában teljesül minden csillagrendszerre, hogy ha kilépünk belőle, akkor biztosan nem tudunk visszajutni.
Minden csillagrendszerről tudjuk, hogy mennyi uránt (melyet üzemanyagként használunk), illetve titánt tudunk bányászni, ha meglátogatjuk. Az urán tárolása körülményes, ezért csak meghatározott mennyiséget tudunk belőle raktározni. Minden féregjáratról tudjuk, hogy mennyi uránt fogyasztunk az áthaladás közben. Szerencsére bármely csillagrendszerben feltölthetjük uránkészletünket egy egységnyi titánért. Kezdetben tele van az üzemanyagtartályunk, és nincs titánunk.
Írjunk programot, amely a standard inputról beolvassa a térképet, valamint az induló- és a célcsillagrendszer sorszámát, és megadja, hogy legföljebb mennyi titánnal érhetünk el a célba, továbbá az ehhez szükséges útvonalat is.
Bemenet: A standard input első sorában öt szám található, szóközökkel elválasztva: a csillagrendszerek ($2\le N\le 10000$) száma, a féregjáratok ($1\le M\le 200000$) száma, az induló- és a célcsillagrendszer sorszáma (a csillagrendszereket 1-től $N$-ig sorszámozzuk), valamint az üzemanyagtartályunk ($1\le K\le 1000000$) kapacitása.
A következő $N$ sor rendre az $\mathrm{1,2,}\text{...}\mathrm{,}N$-edik csillagrendszert írja le két, szóközzel elválasztott egész számmal, melyek megadják a bányászható titán és urán mennyiségét ($0\le T\mathrm{,}U\le 1000000$). Az utolsó $M$ sor rendre az $\mathrm{1,2,}\text{...}\mathrm{,}M$-edik féregjáratot írja le három egész számmal, melyek a járat kezdő- és célcsillagrendszerének sorszáma és az áthaladáshoz szükséges urán mennyisége ($0\le W\le 1000000$).
Feltehetjük, hogy a kezdő- és célcsillagrendszer nem esik egybe, valamint, hogy nincs két olyan féregjárat, melyek ugyanazt a két csillagrendszert kötik össze, továbbá, hogy a féregjáratok kezdő- és végpontja sem esik egybe.
Kimenet: A program írja ki a standard kimenet első sorába, hogy maximum mennyi titánnal érkezhetünk meg célunkhoz. A második sorba írjunk ki egy ehhez szükséges útvonalat is, a következő formában: az első szám legyen az útvonalban szereplő csillagrendszerek száma (beleértve a kezdő- és célcsillagrendszert), aztán az úton szereplő csillagrendszerek sorszámának felsorolása következzen.
Amennyiben nem juthatunk el a célig, akkor a standard kimenet egyetlen sorába a -1 szám kerüljön.
Példák: