Fişierul intrare/ieşire:	peapesimaitulburi.in, peapesimaitulburi.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 18
Autor	Vlad-Andrei Munteanu	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.75 sec	Limită de memorie	300384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pe ape si mai tulburi

Dupa ce au cutreierat peste mari si tari pentru a gasi sensul vietii, un grup de pirati ajunge inapoi pe plaiurile mioritice dezamagiti de nereusita lor. Ajunsi in satul unde au crescut, acestia se duc fiecare la casele lor pentru a se odihni si a-si varsa amarul intr-un pahar de rom. La un moment dat, in toiul noptii, armata regala se aude din departare. Speriati ca ar putea fi prinsi, piratii nostri se gandesc ca trebuie sa paraseasca cat mai repede satul si sa se refugieze. Stiind ca ar putea dura foarte mult pana sa isi gaseasca un nou adapost si cum fiecare din ei are nevoie de o anumita doza de rom (destul de mare am putea adauga) pentru a supravietui, acestia isi dau seama ca inainte de a se indrepta spre una dintre iesirile satului, fiecare dintre ei trebuie sa se opreasca la una dintre casele cu rezerve de rom pentru a se aproviziona. Fiind sub influenta bauturii traditionale, acestia nu numai ca nu mai sunt in stare sa isi dea seama care este drumul optim pentru ei catre iesire, dar nu mai reusesc nici macar sa distinga toate drumurile din sat sau cat de lungi sunt acestea (se gandesc chiar ca ar putea avea lungimi negative). Aflati in adevarat pericol, piratii va cer ajutorul si, in schimb, va vor oferi si voua o sticla de rom (ceea ce este fenomenal pentru ca se stie ca piratii nu sunt chiar asa de darnici, mai ales cand vine vorba despre bautura lor preferata). Acestia va ofera urmatoarele informatii pentru a le putea da un raspuns cat mai bun: numarul de case din sat, numarul de drumuri pe care piratii au reusit sa le distinga, drumurile propriu-zise care sunt de tipul "locuinta sursa, locuinta target, distanta", numarul de pirati, numarul de case de unde acestia se pot aproviziona, numarul de case din care se poate iesi din sat, indicii caselor unde se afla piratii, indicii caselor de unde se poate face aprovizionarea si indicii caselor de unde se poate iesi. Piratii asteapta in schimb sa le spuneti, pentru fiecare dintre ei, drumul minim astfel incat sa se aprovizioneze si apoi sa ajunga la una dintre iesiri. In cazul in care drumul minim este mai mic de -10¹⁸ (numarul cel mai mic pana la care stie un pirat sa numere), acestia va roaga sa afisati "-INF" (fara ghilimele), iar in cazul in care piratul nu are niciun drum valid, va roaga sa afisati "INF" (fara ghilimele).

Date de intrare

Fişierul de intrare peapesimaitulburi.in contine pe primia linie numerele n si m, reprezentand numarul de case si numarul de drumuri oferite de pirati. Urmatoarele m linii contin fiecare cate un triplet de forma x y d cu semnificatia ca exista drum de la casa x la casa y de distanta d. Urmatoarele sase linii contin numarul p, reprezentand numarul de pirati, p numere separate prin cate un spatiu, reprezentand indicii caselor la care se afla fiecare pirat, numarul a, reprezentand numarul de case de unde acestia se pot aproviziona, a numere separate prin cate un spatiu, reprezentand indicii acestor case, numarul i, reprezentand numarul de case de unde se poate iesi din sat, si i numere separate prin cate un spatiu reprezentand indicii acestora.

Date de ieşire

În fişierul de ieşire peapesimaitulburi.out se vor afisa pe p linii raspunsurile pentru fiecare pirat in parte. Linia i va contine raspunsul pentru piratul i.

Restricţii

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 200.000
• 1 ≤ x ≤ n
• 1 ≤ y ≤ n
• -100.000 ≤ d ≤ 100.000
• 1 ≤ p ≤ n
• 1 ≤ a ≤ n
• 1 ≤ i ≤ n
• Toti indicii din input sunt valizi (cuprinsi in intervalul [1, n]).
• Daca exista un drum de la casa u la casa v NU este garantat sa existe un drum si de la casa v la casa u.
• Se garanteaza ca NU exista drum de la nicio casa la ea insasi.
• Se garanteaza ca NU exista mai mult de un drum direct intre oricare doua case.
• Se garanteaza ca daca pentru un drum (x, y, d) exista mai mult de 2500 de perechi de case (u, v) cu proprietatea ca se poate ajunge atat din casa u in casa v cat si din casa v in casa u trecand prin acel drum, deoarece asta inseamna ca sunt foarte multi pirati care il stiu, sansa ca acestia sa ii fi gresit lungimea este de 0%. Cu alte cuvinte, lungimea acestui drum este un numar natural (nu neaparat strict pozitiv).
• Vi se interzice sa incercati sa furati romul unui pirat. In caz contrar, sfarsitul ar putea fi tragic!

Exemplu

Cum se trimit solutii?