Imorgon (den 17 november) firar vi Skuldfria dagen. Vid detta tillfälle bestämde sig $n$ vänner för att äntligen reglera sina ömsesidiga skulder från många tidigare resor. De har alltid registrerat sina utgifter i en app, som nu har sammanfattat och förenklat allt. För varje person visar den ett totalt saldo $a_i$ — positivt om personen har pengar att fordra, eller negativt om personen måste betala tillbaka pengar. Summan av alla visade värden är naturligtvis lika med noll: $\sum_{i=1}^n a_i = 0$. Vi vill planera överföringar (med heltalsvärden) på ett sådant sätt att varje persons saldo blir noll.

De $n$ personerna är sammanbundna av $m$ förtroenderelationer, som beskrivs av tripplar $(u_j, v_j, c_j)$ — personerna $u_j$ och $v_j$ litar tillräckligt mycket på varandra för att endera av dem ska kunna skicka en överföring till den andra med ett värde på högst $c_j$. Personer som inte är direkt sammanbundna av en förtroenderelation kan inte skicka pengar till varandra. Oordnade par $\{u_j, v_j\}$ upprepas inte, och hela förtroendenätverket är sammanhängande — varje par av personer är sammanlänkat via en (möjligen flerstegs) väg av förtroenderelationer.

Appen visar den totala skulden $A$ (ekvivalent med summan av de positiva $a_i$-värdena). I dennapis vänkrets är förtroendenivåerna ganska höga — för varje par som är sammanbundet av en förtroenderelation gäller att $c_j \ge \lceil \frac{A}{2} \rceil$.

Till exempel, för följden $a = (10, -5, 0, 3, -4, -4)$ har vi $A = 5 + 4 + 4 = 10 + 3 = 13$, och därmed $c_j \ge 7$.

Kan denna grupp av $n$ personer komma överens om riktningar och belopp för överföringar för att helt reglera alla skulder — det vill säga göra allas saldo till noll? Skriv ut TAK (ja) eller NIE (nej) för vart och ett av de $t$ oberoende testfallen.

Du kan anta att varje person har tillräckligt med pengar för att genomföra alla nödvändiga överföringar.

Indata

Den första raden innehåller ett heltal $t$ ($1 \le t \le 10^5$), som anger antalet testfall.

Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), som representerar antalet personer respektive antalet förtroenderelationer.

Den andra raden i varje testfall innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), som representerar det ursprungliga saldot för varje person. Minst ett av talen $a_i$ är skilt från noll.

Vi definierar $A = \sum_{i=1}^n \max(0, a_i)$. Av det föregående villkoret följer att $A \ge 1$.

De följande $m$ raderna beskriver förtroenderelationerna; den $j$-te raden innehåller tre heltal $u_j$, $v_j$ och $c_j$ ($1 \le u_j, v_j \le n$; $u_j \ne v_j$; $\lceil \frac{A}{2} \rceil \le c_j \le 10^{15}$). Nätverket av $n$ personer och $m$ förtroenderelationer är sammanhängande, och varje oordnat par $\{u, v\}$ förekommer högst en gång i ett givet testfall.

Summan av alla $n$-värden över alla testfall överstiger inte $10^6$; likaså överstiger summan av alla $m$-värden inte $10^6$.

Utdata

Skriv ut $t$ rader — för varje testfall, skriv ut ordet TAK om det är möjligt att balansera alla konton, eller ordet NIE annars.

Exempel

Indata

3
2 1
20 -20
1 2 10
5 6
0 1 1 1 -3
1 2 2
2 3 3
3 4 5
2 4 7
1 5 2
4 5 2
3 2
1 2 -3
1 2 1000000000000000
2 3 999997235527681

Utdata

NIE
TAK
TAK

Anmärkning

I det första testfallet finns det två personer med saldon $a = (20, -20)$. Den första personen borde skicka en överföring med värde 20 till den andra, men kan skicka högst $c_1 = 10$. Svaret är NIE (nej).

Figuren nedan illustrerar det andra testfallet med saldon $a = (0, 1, 1, 1, -3)$ inskrivna i hörnen och gränserna $c_j$ på kanterna.

Nedan visas två exempel på giltiga överföringsplaner. I båda planerna överskrids inte överföringsgränserna, och alla slutar med saldot 0. Svaret är TAK (ja).