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.

N/A

N/A

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.