Ngày mai (ngày 17 tháng 11) chúng ta kỷ niệm Ngày Không Nợ Nần (Debt-Free Day). Nhân dịp này, $n$ người bạn quyết định thanh toán dứt điểm các khoản nợ chung từ nhiều chuyến đi trước đây. Họ luôn ghi chép chi tiêu của mình trong một ứng dụng, và giờ ứng dụng đó đã tổng hợp cũng như đơn giản hóa mọi thứ. Đối với mỗi người, ứng dụng hiển thị tổng số dư $a_i$ — dương nếu người đó được nợ tiền, hoặc âm nếu người đó phải trả tiền. Tổng của tất cả các giá trị hiển thị tất nhiên bằng không: $\sum_{i=1}^n a_i = 0$. Chúng ta muốn lập kế hoạch chuyển tiền (với giá trị nguyên) sao cho số dư của mỗi người đều trở thành không.

$n$ người được kết nối bởi $m$ mối quan hệ tin cậy, được mô tả bởi các bộ ba $(u_j, v_j, c_j)$ — hai người $u_j$ và $v_j$ tin tưởng nhau đủ để một trong hai người có thể gửi cho người kia một giao dịch chuyển tiền có giá trị tối đa là $c_j$. Những người không được kết nối trực tiếp bởi mối quan hệ tin cậy không thể gửi tiền cho nhau. Các cặp không thứ tự $\{u_j, v_j\}$ không lặp lại, và toàn bộ mạng lưới tin cậy là liên thông — mọi cặp người đều được nối với nhau bởi một đường đi (có thể gồm nhiều bước) các mối quan hệ tin cậy.

Ứng dụng hiển thị tổng số nợ $A$ (tương đương với tổng các giá trị $a_i$ dương). Trong nhóm bạn này, mức độ tin cậy khá cao — với mọi cặp được kết nối bởi mối quan hệ tin cậy, luôn thỏa mãn $c_j \ge \lceil \frac{A}{2} \rceil$.

Ví dụ, với dãy $a = (10, -5, 0, 3, -4, -4)$ ta có $A = 5 + 4 + 4 = 10 + 3 = 13$, do đó $c_j \ge 7$.

Liệu nhóm $n$ người này có thể thống nhất hướng và số tiền chuyển khoản để thanh toán hết mọi khoản nợ — tức là làm cho số dư của mọi người đều bằng không hay không? Hãy in ra TAK (có) hoặc NIE (không) cho mỗi test trong $t$ bộ test độc lập.

Bạn có thể giả sử rằng mỗi người đều có đủ tiền để thực hiện bất kỳ giao dịch chuyển tiền cần thiết nào.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$), biểu thị số lượng bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), lần lượt biểu thị số người và số mối quan hệ tin cậy.

Dòng thứ hai của mỗi bộ test chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), biểu thị số dư ban đầu của mỗi người. Ít nhất một trong các số $a_i$ khác không.

Ta định nghĩa $A = \sum_{i=1}^n \max(0, a_i)$. Từ điều kiện trước suy ra $A \ge 1$.

$m$ dòng tiếp theo mô tả các mối quan hệ tin cậy; dòng thứ $j$ chứa ba số nguyên $u_j$, $v_j$ và $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}$). Mạng lưới gồm $n$ người và $m$ mối quan hệ tin cậy là liên thông, và mỗi cặp không thứ tự $\{u, v\}$ xuất hiện trong một bộ test tối đa một lần.

Tổng tất cả các giá trị $n$ qua các bộ test không vượt quá $10^6$; tương tự, tổng tất cả các giá trị $m$ không vượt quá $10^6$.

Kết quả

In ra $t$ dòng — với mỗi bộ test, in ra từ TAK nếu có thể cân bằng tất cả các tài khoản, hoặc từ NIE trong trường hợp ngược lại.

Ví dụ

Dữ liệu vào

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

Kết quả

NIE
TAK
TAK

Ghi chú

Ở bộ test đầu tiên, có hai người với số dư $a = (20, -20)$. Người thứ nhất cần gửi cho người thứ hai một khoản chuyển tiền trị giá 20, nhưng chỉ có thể gửi tối đa $c_1 = 10$. Câu trả lời là NIE (không).

Hình dưới đây minh họa bộ test thứ hai với số dư $a = (0, 1, 1, 1, -3)$ được viết bên trong các đỉnh, và giới hạn $c_j$ trên các cạnh.

Dưới đây là hai ví dụ về kế hoạch chuyển tiền hợp lệ. Trong cả hai kế hoạch, giới hạn chuyển tiền không bị vượt quá và mọi người đều kết thúc với số dư bằng 0. Câu trả lời là TAK (có).