พรุ่งนี้ (วันที่ 17 พฤศจิกายน) เราฉลองวันปลอดหนี้ (Debt-Free Day) ในโอกาสนี้ เพื่อน $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 (ใช่)