Domani (17 novembre) celebriamo la Giornata Senza Debiti. In questa occasione, $n$ amici hanno deciso di saldare finalmente i loro debiti reciproci accumulati durante molti viaggi passati. Hanno sempre registrato le loro spese in un'app, che ora ha riassunto e semplificato tutto. Per ciascuna persona, l'app mostra un saldo totale $a_i$ — positivo se a quella persona sono dovuti dei soldi, oppure negativo se quella persona deve restituire dei soldi. La somma di tutti i valori mostrati è, ovviamente, uguale a zero: $\sum_{i=1}^n a_i = 0$. Vogliamo pianificare dei trasferimenti (con valori interi) in modo tale che il saldo di ciascuna persona diventi zero.
Le $n$ persone sono collegate da $m$ relazioni di fiducia, descritte da terne $(u_j, v_j, c_j)$ — le persone $u_j$ e $v_j$ si fidano abbastanza l'una dell'altra che una qualsiasi delle due può inviare all'altra un singolo trasferimento di valore al più $c_j$. Le persone non direttamente collegate da una relazione di fiducia non possono inviarsi denaro. Le coppie non ordinate $\{u_j, v_j\}$ non si ripetono e l'intera rete di fiducia è connessa — ogni coppia di persone è collegata da un cammino (eventualmente di più passi) di relazioni di fiducia.
L'app mostra il debito totale $A$ (equivalentemente, la somma dei valori $a_i$ positivi). In questo gruppo di amici i livelli di fiducia sono piuttosto alti — per ogni coppia collegata da una relazione di fiducia vale che $c_j \ge \lceil \frac{A}{2} \rceil$.
Ad esempio, per la sequenza $a = (10, -5, 0, 3, -4, -4)$ abbiamo $A = 5 + 4 + 4 = 10 + 3 = 13$, quindi $c_j \ge 7$.
Può questo gruppo di $n$ persone accordarsi su direzioni e importi dei trasferimenti per saldare completamente tutti i debiti — cioè portare a zero il saldo di tutti? Stampa TAK (sì) oppure NIE (no) per ciascuno dei $t$ casi di test indipendenti.
Puoi assumere che ogni persona disponga di denaro sufficiente per effettuare qualsiasi trasferimento necessario.
Input
La prima riga contiene un intero $t$ ($1 \le t \le 10^5$), che indica il numero di casi di test.
La prima riga di ciascun caso di test contiene due interi $n$ e $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), che rappresentano rispettivamente il numero di persone e il numero di relazioni di fiducia.
La seconda riga di ciascun caso di test contiene $n$ interi $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), che rappresentano il saldo iniziale di ciascuna persona. Almeno uno dei numeri $a_i$ è diverso da zero.
Definiamo $A = \sum_{i=1}^n \max(0, a_i)$. Dalla condizione precedente segue che $A \ge 1$.
Le successive $m$ righe descrivono le relazioni di fiducia; la $j$-esima riga contiene tre interi $u_j$, $v_j$ e $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}$). La rete di $n$ persone e $m$ relazioni di fiducia è connessa e ogni coppia non ordinata $\{u, v\}$ compare in un dato caso di test al più una volta.
La somma di tutti i valori di $n$ sui vari casi di test non supera $10^6$; analogamente, la somma di tutti i valori di $m$ non supera $10^6$.
Output
Stampa $t$ righe — per ciascun caso di test, stampa la parola TAK se è possibile pareggiare tutti i conti, oppure la parola NIE altrimenti.
Esempio
Input
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
Output
NIE TAK TAK
Note
Nel primo caso di test ci sono due persone con saldi $a = (20, -20)$. La prima persona dovrebbe inviare alla seconda un trasferimento di valore 20, ma può inviare al più $c_1 = 10$. La risposta è NIE (no).
La figura seguente illustra il secondo caso di test con i saldi $a = (0, 1, 1, 1, -3)$ scritti all'interno dei vertici e i limiti $c_j$ sugli archi.
Qui sotto sono riportati due esempi di piani di trasferimento validi. In entrambi i piani i limiti di trasferimento non vengono superati e tutti terminano con saldo 0. La risposta è TAK (sì).
