Huomenna (17. marraskuuta) vietämme Velatonta päivää. Tämän kunniaksi $n$ ystävää päätti vihdoin selvittää keskinäiset velkansa monilta menneiltä matkoilta. He ovat aina kirjanneet kulunsa sovellukseen, joka on nyt koonnut ja yksinkertaistanut kaiken. Jokaiselle henkilölle sovellus näyttää kokonaissaldon $a_i$ — positiivisen, jos kyseiselle henkilölle ollaan velkaa, tai negatiivisen, jos kyseisen henkilön täytyy maksaa rahaa takaisin. Kaikkien näytettyjen arvojen summa on tietenkin nolla: $\sum_{i=1}^n a_i = 0$. Haluamme suunnitella (kokonaislukuarvoiset) tilisiirrot siten, että jokaisen henkilön saldoksi tulee nolla.
$n$ henkilöä on yhdistetty $m$ luottamussuhteella, jotka kuvataan kolmikoilla $(u_j, v_j, c_j)$ — henkilöt $u_j$ ja $v_j$ luottavat toisiinsa tarpeeksi, jotta kumpi tahansa heistä voi lähettää toiselle yhden korkeintaan arvoisen $c_j$ siirron. Henkilöt, joita luottamussuhde ei yhdistä suoraan, eivät voi lähettää rahaa toisilleen. Järjestämättömät parit $\{u_j, v_j\}$ eivät toistu, ja koko luottamusverkosto on yhtenäinen — jokaisen henkilöparin välillä on (mahdollisesti monivaiheinen) luottamussuhteiden polku.
Sovellus näyttää kokonaisvelan $A$ (yhtäpitävästi positiivisten $a_i$-arvojen summan). Tässä ystäväpiirissä luottamustaso on varsin korkea — jokaiselle luottamussuhteella yhdistetylle parille pätee $c_j \ge \lceil \frac{A}{2} \rceil$.
Esimerkiksi jonolle $a = (10, -5, 0, 3, -4, -4)$ saadaan $A = 5 + 4 + 4 = 10 + 3 = 13$, joten $c_j \ge 7$.
Voiko tämä $n$ henkilön ryhmä sopia siirtojen suunnista ja summista siten, että kaikki velat saadaan kokonaan kuitattua — eli kaikkien saldoksi tulee nolla? Tulosta TAK (kyllä) tai NIE (ei) jokaiselle $t$:stä riippumattomasta testitapauksesta.
Voit olettaa, että jokaisella henkilöllä on tarpeeksi rahaa kaikkien tarvittavien siirtojen tekemiseen.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $t$ ($1 \le t \le 10^5$), joka ilmaisee testitapausten määrän.
Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), jotka vastaavat henkilöiden määrää ja luottamussuhteiden määrää.
Jokaisen testitapauksen toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), jotka kuvaavat kunkin henkilön alkusaldoa. Vähintään yksi luvuista $a_i$ on nollasta poikkeava.
Määrittelemme $A = \sum_{i=1}^n \max(0, a_i)$. Edellisestä ehdosta seuraa, että $A \ge 1$.
Seuraavat $m$ riviä kuvaavat luottamussuhteita; $j$:s rivi sisältää kolme kokonaislukua $u_j$, $v_j$ ja $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$ henkilön ja $m$ luottamussuhteen muodostama verkosto on yhtenäinen, ja jokainen järjestämätön pari $\{u, v\}$ esiintyy annetussa testitapauksessa korkeintaan kerran.
Kaikkien $n$:n arvojen summa yli testitapausten ei ylitä arvoa $10^6$; samoin kaikkien $m$:n arvojen summa ei ylitä arvoa $10^6$.
Tuloste
Tulosta $t$ riviä — tulosta jokaiselle testitapaukselle sana TAK, jos kaikki tilit on mahdollista tasapainottaa, tai sana NIE muussa tapauksessa.
Esimerkki
Syöte
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
Tuloste
NIE TAK TAK
Huomautus
Ensimmäisessä testitapauksessa on kaksi henkilöä, joiden saldot ovat $a = (20, -20)$. Ensimmäisen henkilön pitäisi lähettää toiselle 20 suuruinen siirto, mutta hän voi lähettää korkeintaan $c_1 = 10$. Vastaus on NIE (ei).
Alla oleva kuva havainnollistaa toista testitapausta, jossa saldot $a = (0, 1, 1, 1, -3)$ on kirjoitettu solmujen sisään ja rajat $c_j$ kaariin.
Alla on kaksi esimerkkiä kelvollisista siirtosuunnitelmista. Kummassakaan suunnitelmassa siirtorajoja ei ylitetä, ja kaikkien loppusaldoksi tulee 0. Vastaus on TAK (kyllä).
