Kraina kapitana Mambeksa składa się z dwóch miast oraz N wiosek. Wioski ponumerowane są od 0 do N-1, natomiast miasta mają numery N oraz N+1. Wioski i miasta połączone są miedzy sobą drogami dwukierunkowymi, przy czym żadna z dróg nie krzyżuje się z inną. Drogi są tak poprowadzone, aby była możliwość dojazdu między dowolną parą miast lub wiosek.
W ostatnim czasie wykryto działania tajemniczej szajki, która zajmuje się przemytem diamentów między miastami. Kapitan pragnie rozprawić się z przemytnikami. W tym celu na drogach postanowił rozmieścić strażników tak, aby uniemożliwić przemytnikom przejazd z jednego miasta do drugiego. Oczywiście aby tego dokonać należy dysponować odpowiednią liczbą strażników. Strażnik może być umieszczony w dowolnym miejscu drogi, przy czym nie może on być umieszczony ani w mieście ani w wiosce. Na drodze można umieścić dowolną liczbę strażników.
Twoim zadaniem jest napisanie programu, który ustali czy jest możliwe rozmieszczenie strażników na drogach w taki sposób, aby uniemożliwić przemyt diamentów pomiędzy miastami.
Dane wejściowe składają się z kilku zestawów danych. Pierwszy wiersz pojedynczego zestawu danych zawiera trzy liczby całkowite N, S, D, oddzielone pojedynczym odstępem, o następującym znaczeniu: N (0 < N ≤ 150) jest liczbą wiosek, S (0 < S ≤ 100000) jest liczbą strażników, natomiast D (D ≤ 5000) jest liczbą dróg w całej krainie. Kolejnych D wierszy opisuje drogi i zawierają one trzy liczy całkowite X, Y, L oddzielone odstępem, gdzie X, Y (0 ≤ X, Y ≤ N+1) są numerami miast lub wiosek miedzy którymi istnieje droga, natomiast L (0 < L ≤ 1000) jest długością drogi. Dane wejściowe zakończone są wierszem zawierającym trzy zera.
Dla każdego zestawu danych wejściowych program powinien wypisać słowo TAK, jeżeli istnieje możliwość rozmieszczenia strażników w taki sposób, aby uniemożliwić przejazd przemytnikom miedzy miastami, lub słowo NIE jeśli nie ma takiej możliwości. Każde z tych słów powinno być napisane dużymi literami.
4 2 7 5 1 1 1 2 3 5 0 1 0 2 6 0 3 2 3 4 1 2 4 1 4 2 7 4 5 1 4 0 2 4 2 1 0 1 3 1 5 1 2 3 2 3 5 1 5 2 9 6 3 1 6 0 2 3 2 2 0 1 3 0 4 2 1 5 3 4 5 2 1 2 4 2 5 3 2 1 3 2 0 1 0 1 1 1 3 1 0 0 0
TAK NIE TAK TAK