Fișierul intrare/ieșire	termite.in, termite.out	Sursă	Lot Sovata 2014
Autor	Andrei Pârvu | Vlad Ionescu	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	1.8 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Termite (lot seniori)

În lipsa prințesei cu ochii verzi, tărâmul ei fermecat a fost invadat de termite! Se știe despre tărâmul fermecat că este organizat sub forma unui graf conex neorientat, în care fiecare muchie are atribuită o lungime. Prințesa nu poate să combată această invazie, însă ea a aflat informații prețioase despre aceste termite. Se știe că invazia a pornit simultan din exact K noduri, la un moment de timp pe care îl vom nota cu 0. Aceste termite, o dată aflate într-un nod, îl manâncă instant, se înmultesc și pornesc pe muchiile incidente nodului către nodurile vecine. Astfel, dacă o termită ajunge într-un nod la un moment de timp T, tot în același moment termitele îl vor mânca, se vor înmulți și vor porni către celelalte noduri. Prințesa mai știe de altfel că timpul lor de deplasare este constant și că acestea parcurg o muchie de lungime L exact în L secunde. Un nod o dată mâncat, acesta va dispărea din graf, însă nu neapărat și muchiile incidente lui (muchia va ramâne în graf atâta timp cât este incidentă cel puțin unui nod). Altfel zis, o muchie va dispărea doar atunci când ambele noduri de la capete ei vor fi mâncate.

Prințesa nu își poate salva întregul regat, însă ar dori să știe dacă ar putea salva unele comori care se află în anumite noduri ale grafului. Astfel, ea va va pune Q întrebări de forma A B T cu următoarea semnificație: știind că prințesa se află la momentul T în nodul A, iar comoara se află în nodul B, câte secunde se vor scurge până când nu va mai exista niciun drum între ea și comoară (aceasta se poate întampla și în cazurile în care nodul A sau nodul B este mâncat). Dacă încă din momentul T nu există niciun drum între cele două noduri, atunci se va afișa 0.

Cerință

Ajutați-o pe prințesă, răspunzând corect la toate cele Q întrebari.

Date de intrare

Fișierul de intrare termite.in conține pe prima linie 4 numere naturale: n – numărul de noduri ale grafului, m – numărul de muchii ale grafului, k – numărul de noduri din care au pornit termitele și Q – numărul de întrebări. A doua linie a fișierului va conține k valori, semnificând indicele nodurilor unde au apărut în momentul 0 termitele. Următoarele m linii vor conține câte 3 valori: a, b și L, însemnând că între nodurile a și b există o muchie de lungime L. Următoarele Q linii din fișierul de intrare vor reprezenta query-urile, în forma A B T, însemnand câte secunde mai are prințesa începând de la momentul de timp T până când nu va mai exista drum între nodurile A și B.

Date de ieșire

Fișierul de ieșire termite.out va conține Q linii cu câte un singur număr natural reprezentând răspunsurile la cele Q întrebari.

Restricții

• 1 ≤ n, k ≤ 300 000
• 1 ≤ m, Q ≤ 400 000
• Lungimile muchiilor sunt numere naturale mai mici decât 1000.

Exemplu