CF1483D Useful Edges

You are given a weighted undirected graph on $ n $ vertices along with $ q $ triples $ (u, v, l) $ , where in each triple $ u $ and $ v $ are vertices and $ l $ is a positive integer. An edge $ e $ is called useful if there is at least one triple $ (u, v, l) $ and a path (not necessarily simple) with the following properties: - $ u $ and $ v $ are the endpoints of this path, - $ e $ is one of the edges of this path, - the sum of weights of all edges on this path doesn't exceed $ l $ . Please print the number of useful edges in this graph.

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.

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

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.