POLSKI SPOJ

Za górami, za lasami, za rzekami, za morzami jest kraj potężny i bogaty zwany Bajtocją. Panuje tam dobrotliwy król Bajtazar I Wielki, słynny ze swej troski o infrastrukturę kraju. W Bajtocji jest n miast. Władca rozkazał swoim m nadwornym architektom przygotować projekty nowych ponaddźwiękowych traktów konnych. Jako odpowiedź dostał m propozycji, każda z nich składa się z trzech liczb p, k, w, gdzie p i k są miastami końcowymi traktu (trakt łączy te miasta bezpośrednio i nie przechodzi przez inne miasta), a w jest kosztem zbudowania tego traktu. Każdy trakt jest dwukierunkowy. Zamierzeniem króla jest budowa sieci traktów tak, aby można było nimi przejechać między każdymi dwoma miastami, być może odwiedzając po drodze inne miejscowości. Bajtazar jest bardzo oszczędnym królem, więc postanowił zgodzić się tylko na taką sieć, która jest możliwie najtańsza.

Napisz program BAJ, który:
- wczyta liczbę miast, liczbę proponowanych traktów oraz opisy tych traktów ze standardowego wejścia,
- dla każdego traktu określi, czy istnieje taka sieć połączeń między miastami, zgodna z królewskimi rozkazami i w której rozpatrywany trakt, wybudowany za wskazaną kwotę, jest wykorzystywany,
- wypisze na standardowe wyjście zestawienie uzyskanych wyników.

Input

Pierwszy wiersz wejścia zawiera dwie liczby całkowite: n - liczbę miast i m - liczbę proponowanych traktów, rozdzielone jedną spacją i spełniające warunki 2<=n<=7000, 1<=m<=300000. Każdy z kolejnych m wierszy zawiera po trzy liczby całkowite p, k, w rozdzielone pojedynczymi spacjami, opisujące proponowany trakt, przy czym p i k oznaczają miasta będące końcami traktu, zaś w jest ceną budowy tego traktu (1 <= p, k <= n, 1 <= w <= 100000).

Output

W każdym z kolejnych m wierszy należy wypisać jedno ze słów TAK albo NIE, w zależności od tego, czy istnieje plan budowy zgodny z życzeniami króla, czyli taki, że trakt opisany w odpowiednim wierszu jest w nim zawarty, czy też nie

Uwaga: w swoim rozwiązaniu możesz założyć, że istnieje plan budowy zgodny z zaleceniami króla.

Example

Input:
6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3

Output:
TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK

Zadanie pochodzi z Olimpiady Informatycznej dla Gimnazjum z roku szkolnego 2006/2007 z I etapu.