Á morgun (17. nóvember) fögnum við Skuldlausum degi. Af því tilefni ákváðu $n$ vinir að gera loksins upp sínar gagnkvæmu skuldir úr mörgum fyrri ferðum. Þeir skráðu alltaf útgjöld sín í smáforrit sem hefur nú tekið allt saman og einfaldað það. Fyrir hvern einstakling sýnir það heildarstöðu $a_i$ — jákvæða ef viðkomandi á inni pening, eða neikvæða ef viðkomandi þarf að endurgreiða pening. Summa allra birtu gildanna er auðvitað jöfn núlli: $\sum_{i=1}^n a_i = 0$. Við viljum skipuleggja millifærslur (með heiltölugildum) þannig að staða hvers einstaklings verði núll.

Einstaklingarnir $n$ eru tengdir með $m$ trauststengslum sem lýst er með þrenndum $(u_j, v_j, c_j)$ — einstaklingarnir $u_j$ og $v_j$ treysta hvor öðrum nógu vel til að hvor þeirra sem er geti sent hinum eina millifærslu að verðmæti í mesta lagi $c_j$. Fólk sem ekki er beintengt með trauststengslum getur ekki sent hvort öðru peninga. Óröðuð pör $\{u_j, v_j\}$ endurtaka sig ekki og allt traustsnetið er samanhangandi — sérhvert par einstaklinga er tengt með (hugsanlega margra skrefa) veg af trauststengslum.

Smáforritið sýnir heildarskuldina $A$ (jafngilt summu jákvæðra gilda $a_i$). Í þessum vinahópi er traustið nokkuð mikið — fyrir sérhvert par sem tengist með trauststengslum gildir að $c_j \ge \lceil \frac{A}{2} \rceil$.

Til dæmis, fyrir rununa $a = (10, -5, 0, 3, -4, -4)$ höfum við $A = 5 + 4 + 4 = 10 + 3 = 13$, og því $c_j \ge 7$.

Getur þessi hópur $n$ einstaklinga komið sér saman um stefnur og upphæðir millifærslna til að gera upp allar skuldir að fullu — það er að segja, gert stöðu allra að núlli? Prentið TAK (já) eða NIE (nei) fyrir hvert hinna $t$ óháðu prófunartilvika.

Þú mátt gera ráð fyrir að hver einstaklingur eigi næga peninga til að framkvæma allar nauðsynlegar millifærslur.

Inntak

Fyrsta línan inniheldur heiltölu $t$ ($1 \le t \le 10^5$), sem táknar fjölda prófunartilvika.

Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), sem tákna annars vegar fjölda einstaklinga og hins vegar fjölda trauststengsla.

Önnur línan í hverju prófunartilviki inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), sem tákna upphafsstöðu hvers einstaklings. Að minnsta kosti ein af tölunum $a_i$ er ekki núll.

Við skilgreinum $A = \sum_{i=1}^n \max(0, a_i)$. Af fyrra skilyrðinu leiðir að $A \ge 1$.

Næstu $m$ línur lýsa trauststengslunum; $j$-ta línan inniheldur þrjár heiltölur $u_j$, $v_j$ og $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}$). Netið af $n$ einstaklingum og $m$ trauststengslum er samanhangandi, og sérhvert óraðað par $\{u, v\}$ kemur fyrir í mesta lagi einu sinni í gefnu prófunartilviki.

Summa allra gilda $n$ yfir öll prófunartilvik fer ekki yfir $10^6$; sömuleiðis fer summa allra gilda $m$ ekki yfir $10^6$.

Úttak

Prentið $t$ línur — fyrir hvert prófunartilvik skal prenta orðið TAK ef hægt er að jafna alla reikninga, eða orðið NIE annars.

Dæmi

Inntak

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

Úttak

NIE
TAK
TAK

Athugasemd

Í fyrsta prófunartilvikinu eru tveir einstaklingar með stöðurnar $a = (20, -20)$. Fyrri einstaklingurinn ætti að senda þeim síðari millifærslu að verðmæti 20, en getur í mesta lagi sent $c_1 = 10$. Svarið er NIE (nei).

Myndin hér að neðan sýnir annað prófunartilvikið þar sem stöðurnar $a = (0, 1, 1, 1, -3)$ eru skrifaðar inni í hnútunum og mörkin $c_j$ á leggjunum.

Hér að neðan eru tvö dæmi um gildar millifærsluáætlanir. Í báðum áætlununum er ekki farið yfir millifærslumörkin og allir enda með stöðuna 0. Svarið er TAK (já).