Runda 2: Nurek

Limit czasowy: 12 sekund
Limit pamięciowy: 64 MB

Kajtek to zapalony freediver (nurek bezdechowy). Jako cel swojej wakacyjnej podróży wybrał wyspę X, która słynie z sieci podwodnych jaskiń. W każdej jaskini znajduje się wystarczająco dużo powietrza do zaczerpnięcia oddechu. Niektóre z nich połączone są ze sobą w całości wypełnionymi wodą korytarzami.

Przed wyjazdem Kajtek sporządził mapę wszystkich jaskiń i dla każdego korytarza oszacował czas potrzebny na jego przebycie. Niestety, niektóre z połączeń są zbyt długie i Kajtek nie da rady ich przepłynąć (nie starczy mu powietrza). Znając możliwości Kajtka, pomóż mu stwierdzić czy istnieje bezpieczna droga (być może składająca się z wielu korytarzy) między dwoma zadanymi jaskiniami.

Wejście

W pierwszej linii znajdują się dwie liczby oddzielone pojedynczym odstępem n i m (1<=n,m<=1000000) - jest to odpowiednio liczba jaskiń i liczba korytarzy. W następnych m liniach znajdują się opisy korytarzy, po jednym w każdej linii.

Opis korytarza składa się z 3 liczb oddzielonych pojedynczym odstępem a,b,c (1<=a<b<=n, 1<=c<=1000000), który mówi, że jaskinia a jest połączona z jaskinią b i czas potrzebny na jego przebycie to c. Każdym korytarzem można płynąć w obu kierunkach.

W kolejnej linii znajduje się liczba zapytań k (1<=k<=1000000). W następnych k liniach znajdują się zapytania o bezpieczną drogę, po jednym w każdej linii.

Zapytanie składa się z 3 liczb oddzielonych pojedynczym odstępem a,b,c (1<=a<b<=n, 0<=c<=1000000) - jest to odpowiednio numer jaskini początkowej, numer jaskini docelowej i maksymalny czas jaki może wytrzymać Kajtek pod wodą bez oddechu.

Uwaga: Rozmiar danych na wejściu może być bardzo duży. Upewnij się, że Twój program korzysta z wystarczająco szybkich funkcji wczytywania i wypisywania danych, np. scanf i printf.

Wyjście

Twój program powinien wypisać dokładnie k linii. W i-tej linii powinna znaleźć się odpowieź na i-te zapytanie - TAK jeżeli istnieje bezpieczna droga pomiędzy zadanymi jaskiniami, a NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

4 4
1 2 2
2 4 3
2 3 1
3 4 2
4
1 3 2
1 3 1
1 4 2
2 3 1

poprawną odpowiedzią jest:

TAK
NIE
TAK
TAK