Завтра (17 ноября) мы отмечаем День без долгов. По этому случаю $n$ друзей решили наконец рассчитаться по взаимным долгам, накопившимся за множество прошлых поездок. Они всегда записывали свои расходы в приложение, которое теперь всё просуммировало и упростило. Для каждого человека оно показывает итоговый баланс $a_i$ — положительный, если этому человеку должны деньги, или отрицательный, если этот человек должен вернуть деньги. Сумма всех показанных значений, разумеется, равна нулю: $\sum_{i=1}^n a_i = 0$. Мы хотим спланировать переводы (с целыми значениями) таким образом, чтобы баланс каждого человека стал равен нулю.
$n$ человек связаны $m$ отношениями доверия, описываемыми тройками $(u_j, v_j, c_j)$ — люди $u_j$ и $v_j$ доверяют друг другу достаточно, чтобы любой из них мог отправить другому один перевод на сумму не более $c_j$. Люди, не связанные напрямую отношением доверия, не могут переводить деньги друг другу. Неупорядоченные пары $\{u_j, v_j\}$ не повторяются, а вся сеть доверия связна — каждая пара людей соединена (возможно, многошаговым) путём из отношений доверия.
Приложение показывает общий долг $A$ (эквивалентно, сумму положительных значений $a_i$). В этой компании друзей уровень доверия довольно высок — для каждой пары, связанной отношением доверия, выполняется $c_j \ge \lceil \frac{A}{2} \rceil$.
Например, для последовательности $a = (10, -5, 0, 3, -4, -4)$ имеем $A = 5 + 4 + 4 = 10 + 3 = 13$, следовательно, $c_j \ge 7$.
Может ли эта группа из $n$ человек договориться о направлениях и суммах переводов так, чтобы полностью погасить все долги — то есть сделать баланс каждого равным нулю? Выведите TAK (да) или NIE (нет) для каждого из $t$ независимых наборов входных данных.
Можно считать, что у каждого человека достаточно денег для совершения любых необходимых переводов.
Входные данные
Первая строка содержит целое число $t$ ($1 \le t \le 10^5$), обозначающее количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $n$ и $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), представляющих соответственно количество людей и количество отношений доверия.
Вторая строка каждого набора входных данных содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), представляющих начальный баланс каждого человека. Хотя бы одно из чисел $a_i$ отлично от нуля.
Определим $A = \sum_{i=1}^n \max(0, a_i)$. Из предыдущего условия следует, что $A \ge 1$.
Следующие $m$ строк описывают отношения доверия; $j$-я строка содержит три целых числа $u_j$, $v_j$ и $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}$). Сеть из $n$ человек и $m$ отношений доверия связна, и каждая неупорядоченная пара $\{u, v\}$ встречается в данном наборе входных данных не более одного раза.
Сумма всех значений $n$ по всем наборам входных данных не превышает $10^6$; аналогично, сумма всех значений $m$ не превышает $10^6$.
Выходные данные
Выведите $t$ строк — для каждого набора входных данных выведите слово TAK, если можно сбалансировать все счета, или слово NIE в противном случае.
Пример
Входные данные
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
Выходные данные
NIE TAK TAK
Примечание
В первом наборе входных данных есть два человека с балансами $a = (20, -20)$. Первый человек должен отправить второму перевод на сумму 20, но может отправить не более $c_1 = 10$. Ответ — NIE (нет).
На рисунке ниже проиллюстрирован второй набор входных данных, где балансы $a = (0, 1, 1, 1, -3)$ записаны внутри вершин, а ограничения $c_j$ — на рёбрах.
Ниже приведены два примера допустимых планов переводов. В обоих планах ограничения на переводы не превышены, и у всех итоговый баланс становится равным 0. Ответ — TAK (да).
