Morgen (am 17. November) feiern wir den Tag der Schuldenfreiheit. Aus diesem Anlass haben $n$ Freunde beschlossen, endlich ihre gegenseitigen Schulden aus vielen vergangenen Reisen zu begleichen. Sie haben ihre Ausgaben immer in einer App festgehalten, die nun alles zusammengefasst und vereinfacht hat. Für jede Person zeigt sie einen Gesamtsaldo $a_i$ an — positiv, wenn dieser Person Geld geschuldet wird, oder negativ, wenn diese Person Geld zurückzahlen muss. Die Summe aller angezeigten Werte ist natürlich gleich null: $\sum_{i=1}^n a_i = 0$. Wir möchten Überweisungen (mit ganzzahligen Werten) so planen, dass der Saldo jeder Person null wird.

Die $n$ Personen sind durch $m$ Vertrauensbeziehungen verbunden, die durch Tripel $(u_j, v_j, c_j)$ beschrieben werden — die Personen $u_j$ und $v_j$ vertrauen einander genug, dass jede von ihnen der anderen eine Überweisung im Wert von höchstens $c_j$ senden kann. Personen, die nicht direkt durch eine Vertrauensbeziehung verbunden sind, können einander kein Geld senden. Ungeordnete Paare $\{u_j, v_j\}$ wiederholen sich nicht, und das gesamte Vertrauensnetzwerk ist zusammenhängend — jedes Paar von Personen ist durch einen (möglicherweise mehrstufigen) Pfad von Vertrauensbeziehungen verbunden.

Die App zeigt die Gesamtschuld $A$ an (äquivalent dazu die Summe der positiven $a_i$-Werte). In diesem Freundeskreis ist das Vertrauensniveau recht hoch — für jedes durch eine Vertrauensbeziehung verbundene Paar gilt $c_j \ge \lceil \frac{A}{2} \rceil$.

Beispielsweise haben wir für die Folge $a = (10, -5, 0, 3, -4, -4)$ den Wert $A = 5 + 4 + 4 = 10 + 3 = 13$, also $c_j \ge 7$.

Kann sich diese Gruppe von $n$ Personen auf Richtungen und Beträge von Überweisungen einigen, um alle Schulden vollständig zu begleichen — das heißt, den Saldo aller Personen auf null zu bringen? Geben Sie für jeden der $t$ unabhängigen Testfälle TAK (ja) oder NIE (nein) aus.

Sie können davon ausgehen, dass jede Person über genügend Geld verfügt, um alle erforderlichen Überweisungen durchzuführen.

Eingabe

Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 10^5$), die die Anzahl der Testfälle angibt.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), die die Anzahl der Personen bzw. die Anzahl der Vertrauensbeziehungen darstellen.

Die zweite Zeile jedes Testfalls enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), die den Anfangssaldo jeder Person darstellen. Mindestens eine der Zahlen $a_i$ ist ungleich null.

Wir definieren $A = \sum_{i=1}^n \max(0, a_i)$. Aus der vorherigen Bedingung folgt $A \ge 1$.

Die nächsten $m$ Zeilen beschreiben die Vertrauensbeziehungen; die $j$-te Zeile enthält drei ganze Zahlen $u_j$, $v_j$ und $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}$). Das Netzwerk aus $n$ Personen und $m$ Vertrauensbeziehungen ist zusammenhängend, und jedes ungeordnete Paar $\{u, v\}$ kommt in einem gegebenen Testfall höchstens einmal vor.

Die Summe aller $n$-Werte über alle Testfälle hinweg überschreitet $10^6$ nicht; ebenso überschreitet die Summe aller $m$-Werte $10^6$ nicht.

Ausgabe

Geben Sie $t$ Zeilen aus — geben Sie für jeden Testfall das Wort TAK aus, wenn es möglich ist, alle Konten auszugleichen, oder andernfalls das Wort NIE.

Beispiel

Eingabe

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

Ausgabe

NIE
TAK
TAK

Hinweis

Im ersten Testfall gibt es zwei Personen mit den Salden $a = (20, -20)$. Die erste Person sollte der zweiten eine Überweisung im Wert von 20 senden, kann aber höchstens $c_1 = 10$ senden. Die Antwort lautet NIE (nein).

Die folgende Abbildung veranschaulicht den zweiten Testfall, wobei die Salden $a = (0, 1, 1, 1, -3)$ in den Knoten und die Limits $c_j$ an den Kanten stehen.

Unten sind zwei Beispiele für gültige Überweisungspläne dargestellt. In beiden Plänen werden die Überweisungslimits nicht überschritten, und am Ende hat jeder den Saldo 0. Die Antwort lautet TAK (ja).