Besok (17 November) kita merayakan Hari Bebas Utang (Debt-Free Day). Pada kesempatan ini, $n$ orang teman memutuskan untuk akhirnya melunasi utang-piutang bersama mereka dari banyak perjalanan di masa lalu. Mereka selalu mencatat pengeluaran mereka di sebuah aplikasi, yang kini telah merangkum dan menyederhanakan semuanya. Untuk setiap orang, aplikasi menampilkan total saldo $a_i$ — positif jika orang tersebut berhak menerima uang, atau negatif jika orang tersebut harus membayar uang. Jumlah dari semua nilai yang ditampilkan tentu saja sama dengan nol: $\sum_{i=1}^n a_i = 0$. Kita ingin merencanakan transfer (dengan nilai bilangan bulat) sedemikian rupa sehingga saldo setiap orang menjadi nol.
Ke-$n$ orang tersebut dihubungkan oleh $m$ hubungan kepercayaan, yang dijelaskan oleh tripel $(u_j, v_j, c_j)$ — orang $u_j$ dan $v_j$ cukup saling percaya sehingga salah satu dari mereka dapat mengirimkan satu kali transfer kepada yang lain dengan nilai paling banyak $c_j$. Orang-orang yang tidak terhubung langsung oleh hubungan kepercayaan tidak dapat saling mengirim uang. Pasangan tak terurut $\{u_j, v_j\}$ tidak berulang, dan seluruh jaringan kepercayaan terhubung — setiap pasang orang dihubungkan oleh suatu jalur hubungan kepercayaan (yang mungkin terdiri dari beberapa langkah).
Aplikasi menampilkan total utang $A$ (secara ekuivalen, jumlah dari nilai-nilai $a_i$ yang positif). Dalam kelompok pertemanan ini, tingkat kepercayaannya cukup tinggi — untuk setiap pasangan yang terhubung oleh hubungan kepercayaan, berlaku bahwa $c_j \ge \lceil \frac{A}{2} \rceil$.
Sebagai contoh, untuk barisan $a = (10, -5, 0, 3, -4, -4)$ kita memiliki $A = 5 + 4 + 4 = 10 + 3 = 13$, sehingga $c_j \ge 7$.
Dapatkah kelompok $n$ orang ini menyepakati arah dan nominal transfer untuk melunasi semua utang sepenuhnya — yaitu membuat saldo semua orang menjadi nol? Cetak TAK (ya) atau NIE (tidak) untuk masing-masing dari $t$ kasus uji independen.
Anda dapat mengasumsikan bahwa setiap orang memiliki cukup uang untuk melakukan transfer apa pun yang diperlukan.
Masukan
Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 10^5$), yang menyatakan banyaknya kasus uji.
Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le 10^6$), yang masing-masing menyatakan banyaknya orang dan banyaknya hubungan kepercayaan.
Baris kedua dari setiap kasus uji berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $\sum_{i=1}^n a_i = 0$), yang menyatakan saldo awal setiap orang. Setidaknya satu dari bilangan $a_i$ tidak nol.
Kita definisikan $A = \sum_{i=1}^n \max(0, a_i)$. Dari kondisi sebelumnya diperoleh bahwa $A \ge 1$.
$m$ baris berikutnya menjelaskan hubungan kepercayaan; baris ke-$j$ berisi tiga bilangan bulat $u_j$, $v_j$, dan $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}$). Jaringan dari $n$ orang dan $m$ hubungan kepercayaan tersebut terhubung, dan setiap pasangan tak terurut $\{u, v\}$ muncul dalam suatu kasus uji paling banyak satu kali.
Jumlah semua nilai $n$ di seluruh kasus uji tidak melebihi $10^6$; demikian pula, jumlah semua nilai $m$ tidak melebihi $10^6$.
Keluaran
Cetak $t$ baris — untuk setiap kasus uji, keluarkan kata TAK jika memungkinkan untuk menyeimbangkan semua akun, atau kata NIE jika sebaliknya.
Contoh
Masukan
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
Keluaran
NIE TAK TAK
Catatan
Pada kasus uji pertama, terdapat dua orang dengan saldo $a = (20, -20)$. Orang pertama harus mengirim transfer senilai 20 kepada orang kedua, tetapi paling banyak chỉ dapat mengirim $c_1 = 10$. Jawabannya adalah NIE (tidak).
Gambar di bawah mengilustrasikan kasus uji kedua dengan saldo $a = (0, 1, 1, 1, -3)$ tertulis di dalam simpul, dan batas $c_j$ pada sisi-sisinya.
Di bawah ini adalah dua contoh rencana transfer yang valid. Pada kedua rencana tersebut, batas transfer tidak dilampaui, dan setiap orang berakhir dengan saldo 0. Jawabannya adalah TAK (ya).
