Mañana (17 de noviembre) celebramos el Día Libre de Deudas. En esta ocasión, $n$ amigos decidieron saldar por fin sus deudas mutuas de muchos viajes pasados. Siempre registraron sus gastos en una aplicación, que ahora resumió y simplificó todo. Para cada persona, muestra un saldo total $a_i$ — positivo si a esa persona se le debe dinero, o negativo si esa persona debe devolver dinero. La suma de todos los valores mostrados es, por supuesto, igual a cero: $\sum_{i=1}^n a_i = 0$. Queremos planificar transferencias (con valores enteros) de tal manera que el saldo de cada persona pase a ser cero.
Las $n$ personas están conectadas por $m$ relaciones de confianza, descritas mediante ternas $(u_j, v_j, c_j)$ — las personas $u_j$ y $v_j$ confían lo suficiente entre sí como para que cualquiera de ellas pueda enviar a la otra una transferencia de valor a lo sumo $c_j$. Las personas que no están directamente conectadas por una relación de confianza no pueden enviarse dinero entre sí. Los pares no ordenados $\{u_j, v_j\}$ no se repiten, y toda la red de confianza es conexa — cada par de personas está unido por un camino (posiblemente de varios pasos) de relaciones de confianza.
La aplicación muestra la deuda total $A$ (equivalentemente, la suma de los valores $a_i$ positivos). En este grupo de amigos, los niveles de confianza son bastante altos — para cada par conectado por una relación de confianza, se cumple que $c_j \ge \lceil \frac{A}{2} \rceil$.
Por ejemplo, para la secuencia $a = (10, -5, 0, 3, -4, -4)$ tenemos $A = 5 + 4 + 4 = 10 + 3 = 13$, por lo tanto $c_j \ge 7$.
¿Puede este grupo de $n$ personas ponerse de acuerdo sobre las direcciones y los montos de las transferencias para saldar por completo todas las deudas — es decir, hacer que el saldo de todos sea cero? Imprime TAK (sí) o NIE (no) para cada uno de los $t$ casos de prueba independientes.
Puedes suponer que cada persona tiene suficiente dinero para realizar cualquier transferencia necesaria.
Entrada
La primera línea contiene un entero $t$ ($1 \le t \le 10^5$), que denota el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), que representan respectivamente el número de personas y el número de relaciones de confianza.
La segunda línea de cada caso de prueba contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), que representan el saldo inicial de cada persona. Al menos uno de los números $a_i$ es distinto de cero.
Definimos $A = \sum_{i=1}^n \max(0, a_i)$. De la condición anterior se deduce que $A \ge 1$.
Las siguientes $m$ líneas describen las relaciones de confianza; la $j$-ésima línea contiene tres enteros $u_j$, $v_j$ y $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 red de $n$ personas y $m$ relaciones de confianza es conexa, y cada par no ordenado $\{u, v\}$ aparece en un caso de prueba dado a lo sumo una vez.
La suma de todos los valores de $n$ en todos los casos de prueba no supera $10^6$; del mismo modo, la suma de todos los valores de $m$ no supera $10^6$.
Salida
Imprime $t$ líneas — para cada caso de prueba, imprime la palabra TAK si es posible equilibrar todas las cuentas, o la palabra NIE en caso contrario.
Ejemplo
Entrada
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
Salida
NIE TAK TAK
Nota
En el primer caso de prueba, hay dos personas con saldos $a = (20, -20)$. La primera persona debería enviar a la segunda una transferencia de valor 20, pero puede enviar a lo sumo $c_1 = 10$. La respuesta es NIE (no).
La figura de abajo ilustra el segundo caso de prueba con los saldos $a = (0, 1, 1, 1, -3)$ escritos dentro de los vértices, y los límites $c_j$ en las aristas.
A continuación se muestran dos ejemplos de planes de transferencia válidos. En ambos planes no se superan los límites de transferencia y todos terminan con saldo 0. La respuesta es TAK (sí).
