给您一个 $$$n$$$ 顶点上的加权无向图以及 $$$q$$$ 三元组 $$$(u, v, l)$$$,其中每个三元组 $$$u$$$ 和 $$$v$$$ 是顶点,$$$l$$$ 是正整数。如果至少有一个三元组 $$$(u, v, l)$$$ 和一条具有以下属性的路径(不一定简单),则称边 $$$e$$$ 有用:
- $$$u$$$ 和 $$$v$$$ 是该路径的端点,
- $$$e$$$ 是这条路径的边缘之一,
- 该路径上所有边的权重总和不超过 $$$l$$$。
请打印出该图中有用边的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\leq n\leq 600$$$, $$$0\leq m\leq \frac{n(n-1)}2$$$)。
以下 $$$m$$$ 行中的每一行都包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq w\leq 10^9$$$),表示连接顶点的边$$$u$$$ 和 $$$v$$$ 且权重为 $$$w$$$。
下面一行包含唯一的整数 $$$q$$$ ($$$1\leq q\leq \frac{n(n-1)}2$$$) 表示三元组的数量。
以下 $$$q$$$ 行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$l$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq l\leq 10^9$$$) 表示三元组 $$$(u, v, l)$$$。
保证:
- 图表不包含循环或多重边;
- 三元组中的所有对 $$$(u, v)$$$ 也不同。
输出
打印一个整数,表示图中有用边的数量。
示例
输入 #1
4 6 1 2 1 2 3 1 3 4 1 1 3 3 2 4 3 1 4 5 1 1 4 4
输出 #1
5
输入 #2
4 2 1 2 10 3 4 10 6 1 2 11 1 3 11 1 4 11 2 3 11 2 4 11 3 4 9
输出 #2
1
输入 #3
3 2 1 2 1 2 3 2 1 1 2 5
输出 #3
2
注意
在第一个示例中,除了权重 $$$5$$$ 的边之外,每条边都是有用的。
在第二个示例中,只有 $$$1$$$ 和 $$$2$$$ 之间的边有用,因为它属于路径 $$$1-2$$$ 和 $$$10 \leq 11$$$。另一方面,$$$3$$$ 和 $$$4$$$ 之间的边缘没有用。
在第三个示例中,两条边都很有用,因为有一条路径 $$$1-2-3-2$$$ 的长度恰好为 $$$5$$$。请注意,路径可能多次经过一个顶点。