Завтра (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 (так).