Problem E
Autojuhid

Ülesanne

Logistikafirma Loners autojuhid sõidavad alati üksi. Firma dispetšeritele on väga oluline vastata kiiresti ja täpselt klientide küsimustele selle kohta, kas nende kaup on võimalik ohutult linnast $a$ linna $b$ toimetada.

Autojuhi töö nõuab täpsust ja tähelepanu. Sellepärast peavad autojuhid hiljemalt iga $p$ tunni järel hotellis puhkama. Hotellid on olemas kõigis linnades. Kirjutada programm, mis linnade ja neid ühendavate teede andmete põhjal vastab dispetšerite päringutele.

Sisend

Esimesel real on kolm täisarvu: linnade arv $N$, teede arv $M$, dispetšerite päringute arv $U$. Linnad on nummerdatud $1$ kuni $N$.

Järgmisel $M$ real on teede kirjeldused. Igal real on kolm täisarvu $x$, $y$ ja $t$, mis tähendavad, et linnast $x$ linna $y$ sõitmiseks kulub $t$ tundi. Kõik teed on kahesuunalised ja sõiduaeg on mõlemas suunas sama. Sisend on antud nii, et $x < y$. Mistahes kahe linna vahel on ülimalt üks tee.

Järgmisel $U$ real on dispetšerite päringud. Igal real on kolm täisarvu: lähtelinna number $a$, sihtlinna number $b$, maksimaalne tundide arv $p$, mille juht võib puhkamata sõita. Kõigis päringutes kehtib tingimus $a < b$.

Väljund

Iga päringu kohta väljastada eraldi reale sõna $\texttt{TAIP}$ (leedu keeles jah), kui kauba toimetamine linnast $a$ linna $b$ on võimalik. Kui see pole võimalik, väljastada sõna $\texttt{NE}$ (leedu keeles ei).

Sisendi piirangud

• $1 \leq N, M, U \leq 200\, 000$

• $1 \leq x, y, a, b \leq N$

• $1 \leq t, p \leq 10^9$

Alamülesanded

Näited

Kuigi linnade $1$ ja $5$ vahel on ühendus ($1 \rightarrow 3 \rightarrow 5$), tuleks linnade $1$ ja $3$ vahel sõita $9$ tundi, mis on rohkem kui maksimaalselt lubatud $6$ tundi.

Linnade $3$ ja $4$ vahel pole ühendust.

Linnade $2$ ja $4$ vahel on tee, mis on võimalik läbida lubatud sõiduajaga.

5 3 3
1 3 9
2 4 2
3 5 8
1 5 6
3 4 100
2 4 3

NE
NE
TAIP