Byteland

바이트랜드(Byteland)의 위대한 왕 바이트아사르 1세는 강력하고 부유한 나라 바이트랜드를 다스린다. 이 나라에는 $n$개의 도시가 있다. 왕은 나라의 기반 시설을 개선하고자 왕실 건축가들에게 전국을 잇는 고속도로 건설 계획을 세우라고 명령했다. 왕은 $m$개의 제안을 받았으며, 각 제안은 세 개의 수 $p$, $k$, $w$로 표현된다. 여기서 $p$와 $k$는 고속도로의 양 끝 도시이고, $w$는 이 고속도로를 건설하는 비용이다. 각 고속도로는 양방향이며, 양 끝 도시 외의 다른 도시는 지나지 않는다.

왕은 임의의 두 도시 사이를 (필요하면 여러 도시를 거쳐서라도) 오갈 수 있도록 고속도로들을 고르고 싶어 한다. 또한 바이트아사르는 이 고속도로 망을 가능한 한 저렴하게 건설하고 싶어 한다.

다음을 수행하는 프로그램을 작성하여라.

• 표준 입력에서 도시의 수, 제안된 고속도로의 수, 그리고 각 고속도로의 정보를 읽는다.
• 각 고속도로에 대해, 그 고속도로를 포함하면서 왕의 조건을 만족하는 고속도로 망이 존재하는지 판별한다.
• 결과를 표준 출력에 쓴다.

첫째 줄에는 도시의 수 $n$과 제안된 고속도로의 수 $m$이 공백 하나로 구분되어 주어지며, $2 \le n \le 7\,000$, $1 \le m \le 300\,000$을 만족한다. 이어지는 $m$개의 줄에는 각각 세 정수 $p$, $k$, $w$가 공백으로 구분되어 주어지며, 제안된 고속도로 하나를 나타낸다. $p$와 $k$는 고속도로의 양 끝 도시의 번호이고, $w$는 건설 비용이다 ($1 \le p, k \le n$, $1 \le w \le 100\,000$).

출력은 $m$개의 줄로 이루어진다. $i$번째 줄에는, 입력의 $i$번째 고속도로를 포함하면서 왕의 조건을 만족하는 고속도로 망이 존재하면 TAK을, 존재하지 않으면 NIE를 출력한다. 왕의 조건을 만족하는 고속도로 망이 적어도 하나 존재함이 보장된다.