Demain (le 17 novembre), nous célébrons la Journée sans dettes. À cette occasion, $n$ amis ont décidé de régler enfin leurs dettes mutuelles accumulées lors de nombreux voyages passés. Ils ont toujours enregistré leurs dépenses dans une application, qui a maintenant tout résumé et simplifié. Pour chaque personne, elle affiche un solde total $a_i$ — positif si l'on doit de l'argent à cette personne, ou négatif si cette personne doit rembourser de l'argent. La somme de toutes les valeurs affichées est, bien sûr, égale à zéro : $\sum_{i=1}^n a_i = 0$. Nous voulons planifier des virements (à valeurs entières) de telle sorte que le solde de chaque personne devienne nul.
Les $n$ personnes sont reliées par $m$ relations de confiance, décrites par des triplets $(u_j, v_j, c_j)$ — les personnes $u_j$ et $v_j$ se font suffisamment confiance pour que l'une ou l'autre puisse envoyer à l'autre un virement d'une valeur d'au plus $c_j$. Les personnes qui ne sont pas directement reliées par une relation de confiance ne peuvent pas s'envoyer d'argent. Les paires non ordonnées $\{u_j, v_j\}$ ne se répètent pas, et l'ensemble du réseau de confiance est connexe — chaque paire de personnes est reliée par un chemin (éventuellement en plusieurs étapes) de relations de confiance.
L'application affiche la dette totale $A$ (de manière équivalente, la somme des valeurs $a_i$ positives). Dans ce groupe d'amis, les niveaux de confiance sont assez élevés — pour chaque paire reliée par une relation de confiance, on a $c_j \ge \lceil \frac{A}{2} \rceil$.
Par exemple, pour la suite $a = (10, -5, 0, 3, -4, -4)$, nous avons $A = 5 + 4 + 4 = 10 + 3 = 13$, d'où $c_j \ge 7$.
Ce groupe de $n$ personnes peut-il s'entendre sur les sens et les montants des virements pour régler intégralement toutes les dettes — c'est-à-dire ramener le solde de chacun à zéro ? Affichez TAK (oui) ou NIE (non) pour chacun des $t$ cas de test indépendants.
Vous pouvez supposer que chaque personne dispose de suffisamment d'argent pour effectuer tous les virements nécessaires.
Entrée
La première ligne contient un entier $t$ ($1 \le t \le 10^5$), désignant le nombre de cas de test.
La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($2 \le n \le 10^6$ ; $n - 1 \le m \le 10^6$), représentant respectivement le nombre de personnes et le nombre de relations de confiance.
La deuxième ligne de chaque cas de test contient $n$ entiers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$ ; $\sum_{i=1}^n a_i = 0$), représentant le solde initial de chaque personne. Au moins l'un des nombres $a_i$ est non nul.
On définit $A = \sum_{i=1}^n \max(0, a_i)$. De la condition précédente, il découle que $A \ge 1$.
Les $m$ lignes suivantes décrivent les relations de confiance ; la $j$-ième ligne contient trois entiers $u_j$, $v_j$ et $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}$). Le réseau de $n$ personnes et $m$ relations de confiance est connexe, et chaque paire non ordonnée $\{u, v\}$ apparaît au plus une fois dans un cas de test donné.
La somme de toutes les valeurs de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$ ; de même, la somme de toutes les valeurs de $m$ ne dépasse pas $10^6$.
Sortie
Affichez $t$ lignes — pour chaque cas de test, affichez le mot TAK s'il est possible d'équilibrer tous les comptes, ou le mot NIE sinon.
Exemple
Entrée
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
Sortie
NIE TAK TAK
Note
Dans le premier cas de test, il y a deux personnes avec des soldes $a = (20, -20)$. La première personne devrait envoyer à la seconde un virement de valeur 20, mais ne peut envoyer qu'au plus $c_1 = 10$. La réponse est NIE (non).
La figure ci-dessous illustre le deuxième cas de test avec les soldes $a = (0, 1, 1, 1, -3)$ inscrits à l'intérieur des sommets, et les limites $c_j$ sur les arêtes.
Ci-dessous figurent deux exemples de plans de virement valides. Dans les deux plans, les limites de virement ne sont pas dépassées, et tout le monde termine avec un solde égal à 0. La réponse est TAK (oui).
