题目描述

一个简化神经网络是有向无环图，顶点编号1..n，边(i,j)权值为W_ij。每条有向边表示i向j传递信息，无重边和自环。入度为0的点为输入神经元，出度为0的点为输出神经元；一个孤立点同时属于两者。

输入层神经元的有效状态就是输入给出的C_i，不扣除它的阈值。其他神经元初始状态为0，接收所有前驱信息后，有效状态为

$$C_i=\max\left(0,\sum_{(j,i)\in E}W_{ji}C_j-U_i\right).$$

只有兴奋神经元（有效状态大于0）向后继传递信号；平静神经元不传递任何信号，不能把负状态继续传播。按拓扑依赖计算整个网络最终的有效状态，输出所有兴奋的输出神经元。

输入

第一行n,p。接下来n行，第i行给出初始状态和阈值U_i。非输入层初始状态必须为0。接下来p行i,j,W_ij，表示有向边i→j。

输出

按编号升序输出兴奋的输出神经元，每行编号和有效状态。若没有，输出NULL。输入层阈值不影响输入状态。

数据范围

1≤n≤200，0≤p≤n(n-1)/2；图保证有向无环、无重边和自环。输入状态及阈值为0..10^6的整数，非输入层初始状态为0；-1000≤W_ij≤1000。保证每个非输入点的U_i加上各前驱贡献绝对值之和≤10^15，所有运算可用有符号64位整数精确完成。

输入样例

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

输出样例

3 1
4 1
5 1