#P17977. Finances

Finances

Finances

题目描述

有 nn 位朋友需要结清债务。第 ii 位朋友的净余额为 aia_i:正值表示应收款,负值表示应付款。所有净余额之和为零,且至少一个余额非零。

他们之间有 mm 对信任关系。第 jj 对关系由 (uj,vj,cj)(u_j,v_j,c_j) 表示:两人可以选择一个方向,进行一笔金额为整数、至多为 cjc_j 的转账,也可以不转账。没有直接信任关系的两人不能直接转账。最终希望每个人实际收到的金额减去转出的金额等于其初始净余额,从而结清所有债务。

令总债务为

A=∑i=1nmax⁡(0,ai).A=\sum_{i=1}^{n}\max(0,a_i).

保证每条信任关系的上限都满足

cj≥⌈A2⌉.c_j\ge\left\lceil\frac A2\right\rceil.

信任关系构成连通无向图,无重边、无自环。可以假设每个人都有足够的钱执行安排的转账,无须考虑转账的先后次序。

判断是否存在一种转账方案,使所有债务都得到结清。只需要回答能否实现,不需要输出方案。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例中,第一行两个整数 n,mn,m。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 mm 行,每行三个整数 uj,vj,cju_j,v_j,c_j,描述一对信任关系。

输出格式

每个测试用例输出一行:能结清所有债务时输出 TAK,否则输出 NIE。

数据范围

  • 1≤t≤1051\le t\le10^5;
  • 2≤n≤1062\le n\le10^6,n−1≤m≤106n-1\le m\le10^6;
  • −109≤ai≤109-10^9\le a_i\le10^9,∑ai=0\sum a_i=0,至少一个 ai≠0a_i\ne0;
  • 1≤uj,vj≤n1\le u_j,v_j\le n,uj≠vju_j\ne v_j;
  • ⌈A/2⌉≤cj≤1015\lceil A/2\rceil\le c_j\le10^{15};
  • 图连通且无重边;
  • 所有测试用例的 nn 之和不超过 10610^6,mm 之和也不超过 10610^6。

样例

输入

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

样例说明

第一组需要在两人之间转账 2020,但唯一一条信任关系只允许转账至多 1010,因此无解。