题目描述

给出一张有向无环图 $G = (V, E)$。其中入度为 $0$ 的点叫源点，出度为 $0$ 的点叫汇点。可能存在多个源点，多个汇点。

每个点有两个属性。记点 $i$ 的两个属性分别为 $A_i、B_i$。其中 $A_i$ 表示该点的信号强度，$B_i$ 表示该点的信号损失指数。

初始时，只有源点具有信号，即输入数据中 $A_i≠0$ 则表示点 $i$ 是源点，其他点均无信号。

对于任意点 $i$ ，当 $A_i > 0$ 时，它可以沿有向边向邻点传输信号，否则无法传输。

对于任意点 $j$，可能有多个点向它传输信号，并且信号在传输过程中没有损失，但在到达该点被接收时会有损失，总损失值为 $B_j$。

这样，对于点 $j$ ，它最终可以接收到的总信号强度等于它接收到的信号强度之和减去信号损失指数，即：

$$A_j = \left(\sum\limits_{(i,j) \in E} W_{ij}A_{i}\right)-B_{j} $$

其中 $(i,j)$ 表示从点 $i$ 到点 $j$ 有一条有向边，权值为 $W_{ij}$。权值可能为负。

当点 $j$ 接收信号后，如果信号强度大于 0，并且存在后继节点，它会继续将信号传输给它的后继点。

现在请你计算最终有多少个汇点可以接收到信号（最终信号强度为正数）？

输入格式

第一行：两个整数 $N, M$。

接下来 $N$ 行，每行两个整数 $A_i, B_i$。

再下面 $M$ 行，每行三个整数 $i, j, W_{ij}$，表示从点 $i$ 到点 $j$ 有一条权值为 $W_{ij}$ 的有向边。

输入数据保证计算过程中不会出现高精度运算。

输出格式

包含若干行，每行两个整数，分别表示能够接收到信号的汇点的编号及最终信号强度。答案应按照点编号从小到大的顺序依次输出。

若没有汇点能接收到信号，则输出 -1。

样例输入

7 8
1 0
2 0
0 0
0 2
0 1
0 3
0 1
1 3 1
1 4 1
2 3 1
2 4 1
3 5 1
3 7 1
4 6 -2
4 7 1

样例输出

5 2
7 3

数据范围

$1 ≤ N ≤ 100, 0 ≤ A_i, B_i ≤ 10^5, 1 ≤ i, j ≤ N, |W_{ij}| ≤ 10^5$