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$ 个顶点的带权无向图，以及 $q$ 个三元组 $(u, v, l)$，其中每个三元组中 $u$ 和 $v$ 是顶点，$l$ 是一个正整数。一条边 $e$ 被称为有用边，当且仅当存在至少一个三元组 $(u, v, l)$ 和一条（不一定简单）路径，满足以下条件：

• 该路径的两个端点为 $u$ 和 $v$，
• 边 $e$ 是该路径中的一条边，
• 该路径上所有边的权重之和不超过 $l$。

请输出该图中有用边的数量。

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.

第一行包含两个整数 $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)$ 对互不相同。

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.

在第一个例子中，除权重为 $5$ 的边外，其余每条边都是有用的。

在第二个例子中，仅有顶点 $1$ 与 $2$ 之间的边是有用的，因为它属于路径 $1\text{-}2$，且满足 $10 \leq 11$。而顶点 $3$ 与 $4$ 之间的边则不是有用的。

在第三个例子中，两条边都是有用的，因为存在一条长度恰好为 $5$ 的路径 $1\text{-}2\text{-}3\text{-}2$。请注意，该路径可以多次经过同一顶点。