Problem : 63 - 宅心仁厚

Problem Statistics

Solved Member: 32　　Submission: 100　　User Tried: 34

Statement:

瀚瀚國國王要實施一個很棒的政策。

為了讓瀚瀚國可以興盛，他決定修築一個偉大的世外桃源，但規劃是一件非常麻煩的事情，每天每天，他都有很多的事情要處理，因此他將當初的設計圖交給了你，要你幫忙。

為了節省費用，只需要盡量讓任意兩個城市可以連通就好了，也就是用最少的道路使 n 個城市皆互相連通，現在你有每一條道路的建設成本，由於財政困難，瀚瀚國國王希望把道路建設的成本降到最低。當你準備來個greedy時，你意外發現有很多組解！也就是說你有多種選法，可以使建設的成本最低，現在請你將所有有可能被興建的道路找出來。

Input:Output:

第一行為兩個正整數n m (1 ≤ n ≤ 7000, 1 ≤ m ≤ 300000)，分別代表的是有多少城市與道路。
接下來有m行，每行三個正整數u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 100000)，代表城市u到城市v有一條興建成本為w的雙向道路。

請輸出m行，分別代表第i條道路有沒有被考慮的可能，若有輸出"TAK"，若沒有則輸出"NIE" (不包括雙引號)。

Sample Input:Sample Output:

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

TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK

Source:

OIG 1 Stage 1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32767kb
1-ocen	1000ms	32767kb
1	1500ms	32767kb	9
2-ocen	1000ms	32767kb
2	1500ms	32767kb	9
3-ocen	1000ms	32767kb
3	1500ms	32767kb	9
4	1000ms	32767kb	9
5	1000ms	32767kb	9
6	1000ms	32767kb	9
7	1500ms	32767kb	9
8	1700ms	32767kb	9
9	2000ms	32767kb	9
10	2500ms	32767kb	9
11	3000ms	32767kb	10