Jutro (17 listopada) obchodzimy Dzień bez Długów. Z tej okazji $n$ znajomych postanowiło wreszcie rozliczyć swoje wzajemne długi z wielu wspólnych wyjazdów. Zawsze zapisywali wydatki w aplikacji, która teraz wszystko podsumowała i uprościła. Dla każdej osoby wyświetla ona łączny bilans $a_i$ — dodatni, jeśli tej osobie należy się zwrot pieniędzy, lub ujemny, jeśli ta osoba musi oddać pieniądze. Suma wszystkich wyświetlanych wartości jest oczywiście równa zeru: $\sum_{i=1}^n a_i = 0$. Chcemy zaplanować przelewy (o wartościach całkowitych) w taki sposób, aby bilans każdej osoby stał się równy zero.

$n$ osób jest połączonych $m$ relacjami zaufania, opisanymi trójkami $(u_j, v_j, c_j)$ — osoby $u_j$ oraz $v_j$ ufają sobie na tyle, że każda z nich może wysłać drugiej jeden przelew o wartości co najwyżej $c_j$. Osoby niepołączone bezpośrednio relacją zaufania nie mogą przesyłać sobie pieniędzy. Nieuporządkowane pary $\{u_j, v_j\}$ nie powtarzają się, a cała sieć zaufania jest spójna — każda para osób jest połączona (być może wieloetapową) ścieżką relacji zaufania.

Aplikacja wyświetla łączny dług $A$ (równoważnie: sumę dodatnich wartości $a_i$). W tej grupie znajomych poziom zaufania jest dość wysoki — dla każdej pary połączonej relacją zaufania zachodzi $c_j \ge \lceil \frac{A}{2} \rceil$.

Na przykład dla ciągu $a = (10, -5, 0, 3, -4, -4)$ mamy $A = 5 + 4 + 4 = 10 + 3 = 13$, a zatem $c_j \ge 7$.

Czy ta grupa $n$ osób może ustalić kierunki i kwoty przelewów tak, aby w pełni rozliczyć wszystkie długi — to znaczy sprawić, by bilans każdego wynosił zero? Wypisz TAK lub NIE dla każdego z $t$ niezależnych przypadków testowych.

Możesz założyć, że każda osoba ma wystarczająco dużo pieniędzy, aby wykonać dowolne potrzebne przelewy.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^5$), oznaczającą liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), oznaczające odpowiednio liczbę osób oraz liczbę relacji zaufania.

Drugi wiersz każdego przypadku testowego zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), reprezentujących początkowy bilans każdej osoby. Co najmniej jedna z liczb $a_i$ jest niezerowa.

Definiujemy $A = \sum_{i=1}^n \max(0, a_i)$. Z poprzedniego warunku wynika, że $A \ge 1$.

Kolejne $m$ wierszy opisuje relacje zaufania; $j$-ty wiersz zawiera trzy liczby całkowite $u_j$, $v_j$ oraz $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}$). Sieć $n$ osób i $m$ relacji zaufania jest spójna, a każda nieuporządkowana para $\{u, v\}$ pojawia się w danym przypadku testowym co najwyżej raz.

Suma wszystkich wartości $n$ we wszystkich przypadkach testowych nie przekracza $10^6$; podobnie suma wszystkich wartości $m$ nie przekracza $10^6$.

Wyjście

Wypisz $t$ wierszy — dla każdego przypadku testowego wypisz słowo TAK, jeśli można wyrównać wszystkie rachunki, lub słowo NIE w przeciwnym razie.

Przykład

Wejście

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

Wyjście

NIE
TAK
TAK

Uwaga

W pierwszym przypadku testowym są dwie osoby o bilansach $a = (20, -20)$. Pierwsza osoba powinna wysłać drugiej przelew o wartości 20, ale może wysłać co najwyżej $c_1 = 10$. Odpowiedź to NIE.

Rysunek poniżej ilustruje drugi przypadek testowy z bilansami $a = (0, 1, 1, 1, -3)$ wpisanymi wewnątrz wierzchołków oraz limitami $c_j$ na krawędziach.

Poniżej przedstawiono dwa przykładowe poprawne plany przelewów. W obu planach limity przelewów nie są przekroczone i każdy kończy z bilansem 0. Odpowiedź to TAK.