polski
Task Byteland (baj)
Byteland
Memory limit: 32 MB
King Byteasar I the Great is the ruler of a mighty and rich country of Byteland.
There are 
towns in the country.
King Byteasar would like to improve the infrastructure of Byteland and has ordered
the royal architects to prepare plans for building highways across the country.
He has received 
proposals, each of which is described by three numbers 
, 
, 
,
where 
and 
are the towns being the endpoints of the highway, and 
denotes the cost
of building this highway.
Each highway is bidirectional and does not visit any town except for its endpoints.
The king would like to choose the highways so that there exists at least one way of travelling between any pair of towns, possibly by visiting several towns along the way. Byteasar would like to build the highway network as cheaply as possible.
Task
Write a program which:
- reads from the standard input the number of towns, the number of proposed highways and the descriptions of these highways,
- finds out, for each highway, whether there exists a highway network containing this highway and satisfying Byteasar's requirements,
- writes the results to the standard output.
Input
The first line of the input contains two integers: the number of towns, 
, and the number
of proposed highways, 
, separated with a single space and satisfying the conditions:
, 
.
Each of the following 
lines contains three space-separated integers 
, 
, 
,
describing the proposed highway.
Here 
and 
denote the numbers of towns which are endpoints of the highway,
and 
is the price of the highway
(
, 
).
Output
The output should consist of 
lines.
The 
-th of those lines should contain a word "TAK" or "NIE", depending on whether
there exists a highway network satisfying Byteasar's requirements containing the 
-th highway from the input.
You can safely assume that there exists at least one highway network satisfying Byteasar's requirements.
Example
For the input data:
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
the correct result is:
TAK TAK TAK NIE TAK NIE TAK TAK TAK TAK
Task author: Wojciech Smietanka.