I morgen (17. november) feirer vi Gjeldfri dag. I den anledning bestemte $n$ venner seg for endelig å gjøre opp sin gjensidige gjeld fra mange tidligere turer. De har alltid registrert utgiftene sine i en app, som nå har oppsummert og forenklet alt. For hver person viser den en totalsaldo $a_i$ — positiv hvis personen har penger til gode, eller negativ hvis personen må betale tilbake penger. Summen av alle viste verdier er selvfølgelig lik null: $\sum_{i=1}^n a_i = 0$. Vi ønsker å planlegge overføringer (med heltallsverdier) slik at hver persons saldo blir null.
De $n$ personene er knyttet sammen av $m$ tillitsforhold, beskrevet ved tripler $(u_j, v_j, c_j)$ — personene $u_j$ og $v_j$ stoler nok på hverandre til at hvem som helst av dem kan sende den andre én overføring med verdi høyst $c_j$. Personer som ikke er direkte knyttet sammen av et tillitsforhold, kan ikke sende penger til hverandre. Uordnede par $\{u_j, v_j\}$ gjentas ikke, og hele tillitsnettverket er sammenhengende — hvert par av personer er knyttet sammen av en (muligens flertrinns) sti av tillitsforhold.
Appen viser den totale gjelden $A$ (ekvivalent med summen av positive $a_i$-verdier). I denne vennegjengen er tillitsnivået ganske høyt — for hvert par knyttet sammen av et tillitsforhold gjelder det at $c_j \ge \lceil \frac{A}{2} \rceil$.
For eksempel, for følgen $a = (10, -5, 0, 3, -4, -4)$ har vi $A = 5 + 4 + 4 = 10 + 3 = 13$, og dermed $c_j \ge 7$.
Kan denne gruppen på $n$ personer bli enige om retninger og beløp for overføringer for å gjøre opp all gjeld fullstendig — det vil si gjøre alles saldo lik null? Skriv ut TAK (ja) eller NIE (nei) for hvert av de $t$ uavhengige testtilfellene.
Du kan anta at hver person har nok penger til å utføre alle nødvendige overføringer.
Inndata
Den første linjen inneholder et heltall $t$ ($1 \le t \le 10^5$), som angir antallet testtilfeller.
Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), som representerer henholdsvis antallet personer og antallet tillitsforhold.
Den andre linjen i hvert testtilfelle inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), som representerer startsaldoen til hver person. Minst ett av tallene $a_i$ er ulik null.
Vi definerer $A = \sum_{i=1}^n \max(0, a_i)$. Fra den foregående betingelsen følger det at $A \ge 1$.
De neste $m$ linjene beskriver tillitsforholdene; den $j$-te linjen inneholder tre heltall $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}$). Nettverket av $n$ personer og $m$ tillitsforhold er sammenhengende, og hvert uordnet par $\{u, v\}$ forekommer høyst én gang i et gitt testtilfelle.
Summen av alle $n$-verdier på tvers av testtilfellene overstiger ikke $10^6$; på samme måte overstiger summen av alle $m$-verdier ikke $10^6$.
Utdata
Skriv ut $t$ linjer — for hvert testtilfelle, skriv ut ordet TAK hvis det er mulig å balansere alle kontoer, eller ordet NIE ellers.
Eksempel
Inndata
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
Merk
I det første testtilfellet er det to personer med saldoer $a = (20, -20)$. Den første personen burde sende den andre en overføring med verdi 20, men kan sende høyst $c_1 = 10$. Svaret er NIE (nei).
Figuren nedenfor illustrerer det andre testtilfellet med saldoene $a = (0, 1, 1, 1, -3)$ skrevet inne i nodene, og grensene $c_j$ på kantene.
Nedenfor vises to eksempler på gyldige overføringsplaner. I begge planene overskrides ikke overføringsgrensene, og alle ender opp med saldo 0. Svaret er TAK (ja).
