Problem E
Fahrerinnen

Aufgabe

Die weltweit aktive Logistikfirma Loners hat ihren Namen daher, dass ihre Fahrerinnen immer alleine fahren. Die Chefinnen finden es sehr wichtig, Kundenanfragen, ob Güter von Stadt $a$ sicher nach Stadt $b$ transportiert werden können, schnell und korrekt beantworten zu können.

Die Arbeit der Fahrerinnen verlangt einen hohen Grad an Verantwortung und Wachsamkeit. Daher müssen sie sich nicht seltener als mindestens alle $p$ Stunden in einem Hotel ausruhen. Hotels gibt es in jeder Stadt. Schreibe ein Programm, das die Informationen über die Städte und die Straßen dazwischen verwendet und damit die Anfragen der Chefinnen bearbeitet.

Eingabe

Die erste Zeile enthält drei ganze Zahlen, jeweils durch ein Leerzeichen getrennt: $N$ - die Anzahl der Städte, $M$ - die Anzahl der Straßen und $U$ - die Anzahl der Anfragen. Die Städte sind von $1$ bis $N$ nummeriert.

Darauf folgen $M$ Zeilen, die die Information über die Wege enthalten. Jede dieser Zeilen besteht aus 3 ganzen Zahlen, jeweils durch Leerzeichen getrennt: $x$, $y$ und $t$. Das gibt an, dass es $t$ Zeit benötigt, um von Stadt $x$ nach Stadt $y$ zu fahren. Alle Wege sind beidseitig befahrbar und benötigen gleich viel Zeit in beide Richtungen. Es gilt also immer $x < y$ und zwischen je zwei Städten kann es höchstens eine Verbindung geben.

Die darauffolgenden $U$ Zeilen beschreiben die Anfragen der Chefinnen. Jede dieser $U$ Zeilen besteht aus je drei Zahlen: $a$ - die Nummer der Ausgangsstadt $b$ - die Nummer der Zielstadt $p$ - die maximale Zeit, die der Fahrer ohne Einkehr in ein Hotel fahren kann. Es gilt immer $a < b$.

Ausgabe

Gib für jede Anfrage auf je einer separaten Zeile $\texttt{TAIP}$ (litauisch für ja) aus, falls der Fahrer die Güter sicher von Stadt $a$ nach $b$ transportieren kann. Ist dies nicht möglich, so muss dein Programm $\texttt{NE}$ (litauisch für nein) ausgeben.

Beschränkungen

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

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

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

Teilaufgaben

Beispiele

Obwohl es Straßen zwischen den Städten 1 und 5 gibt ($1 \rightarrow 3 \rightarrow 5$), müsste die Fahrerin zwischen den Städten 1 und 3 9 Stunden lang fahren und damit länger als die maximal erlaubten 6 Stunden.

Es gibt keine Straße zwischen den Städten 3 und 4.

Es gibt eine direkte Straße zwischen den Städten 2 und 4. Es ist möglich, in der erlaubten Zeit diesen Weg zu fahren.

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

NE
NE
TAIP