题目描述

一个信号传播网络由 $n$ 个节点（神经元）组成，节点之间通过有向边连接，整个网络构成一张有向无环图（DAG）。网络按层次组织：输入层、若干中间层、输出层，信息只从上一层向下一层传递。

每个神经元 $i$ 拥有两个参数：当前状态 $C_i$ 和阈值 $U_i$。网络按如下规则运作：

$$C_i=\left(\sum\limits_{(j,i) \in E} W_{ji}\cdot C_{j}\right)-U_{i}$$

其中 $W_{ji}$ 是从 $j$ 到 $i$ 的有向边的权值（可为负数），求和遍历所有指向 $i$ 的边。当 $C_i \gt 0$ 时，该神经元被激活，会将强度为 $C_i$ 的信号沿出边传递给下一层；若 $C_i \le 0$，则不传递任何信号。

输入层神经元在初始时刻被赋予一个非零状态 $C_i$（由输入给出），其余神经元的初始状态均为 $0$。信号在网络中逐层传播，直到所有神经元处理完毕。请输出最终处于激活状态的输出层神经元（没有任何出边的节点）的状态值。

输入格式

第一行两个整数 $n$（$1 \le n \le 100$）和 $p$，分别表示神经元个数和有向边条数。

接下来 $n$ 行，每行两个整数，第 $i$ 行为神经元 $i$ 的初始状态 $C_i$ 和阈值 $U_i$。非输入层神经元的 $C_i$ 必然为 $0$。

再接下来 $p$ 行，每行三个整数 $i, j, W_{ij}$（$|W_{ij}| \le 10^9$），表示从 $i$ 到 $j$ 有一条权值为 $W_{ij}$ 的有向边。

输出格式

按编号从小到大输出每个处于激活状态的输出层神经元，每行两个整数 $i$ 和 $C_i$，以空格分隔。若不存在激活的输出层神经元，输出 NULL。

样例

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

</p>

提示

网络保证为有向无环图，信号传播顺序由拓扑序决定。注意 $W_{ij}$ 可为负值，激活判定仅看最终 $C_i$ 是否严格大于 $0$。