Ертең (17 қараша) біз القарызсыз күнді (Debt-Free Day) атап өтеміз. Осыған орай $n$ дос өткен көптеген сапарлардан жиналған өзара қарыздарын толықтай жабуды ұйғарды. Олар шығындарын әрдайым қосымшаға жазып отырған, ал енді қосымша бәрін қорытындылап, ықшамдап берді. Әр адам үшін ол жалпы теңгерімді $a_i$ көрсетеді — егер ол адамға ақша тиесілі болса оң, ал егер ол адам ақша қайтаруы керек болса теріс. Көрсетілген барлық мәндердің қосындысы, әрине, нөлге тең: $\sum_{i=1}^n a_i = 0$. Біз әр адамның теңгерімі нөлге тең болатындай етіп (бүтін мәнді) аударымдарды жоспарлағымыз келеді.

$n$ адам $(u_j, v_j, c_j)$ үштіктерімен сипатталатын $m$ сенім қатынасымен байланысқан — $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$ адамнан тұратын топ барлық қарыздарды толық өтеу үшін — яғни әркімнің теңгерімін нөлге теңестіру үшін — аударымдардың бағыттары мен сомалары туралы келісе ала ма? Тәуелсіз $t$ тест жағдайының әрқайсысы үшін TAK (иә) немесе NIE (жоқ) сөзін шығарыңыз.

Әр адамда кез келген қажетті аударымды жасауға жеткілікті ақша бар деп есептей аласыз.

Кіріс деректер

Бірінші жолда тест жағдайларының санын білдіретін бүтін $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 (иә).