Useful Edges

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n\leq 600$$$, $$$0\leq m\leq \frac{n(n-1)}2$$$).

Each of the following $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq w\leq 10^9$$$), denoting an edge connecting vertices $$$u$$$ and $$$v$$$ and having a weight $$$w$$$.

The following line contains the only integer $$$q$$$ ($$$1\leq q\leq \frac{n(n-1)}2$$$) denoting the number of triples.

Each of the following $$$q$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$l$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq l\leq 10^9$$$) denoting a triple $$$(u, v, l)$$$.

It's guaranteed that:

• the graph doesn't contain loops or multiple edges;
• all pairs $$$(u, v)$$$ in the triples are also different.

Output:

Print a single integer denoting the number of useful edges in the graph.

Sample Input:

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

Sample Output:

5

Sample Input:

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

Sample Output:

1

Sample Input:

3 2
1 2 1
2 3 2
1
1 2 5

Sample Output:

2

Note:

In the first example each edge is useful, except the one of weight $$$5$$$.

In the second example only edge between $$$1$$$ and $$$2$$$ is useful, because it belongs to the path $$$1-2$$$, and $$$10 \leq 11$$$. The edge between $$$3$$$ and $$$4$$$, on the other hand, is not useful.

In the third example both edges are useful, for there is a path $$$1-2-3-2$$$ of length exactly $$$5$$$. Please note that the path may pass through a vertex more than once.