CF449B.Jzzhu and Cities

Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city u__i to v__i (and vise versa) using the i-th road, the length of this road is x__i. Finally, there are k train routes in the country. One can use the i-th train route to go from capital of the country to city s__i (and vise versa), the length of this route is y__i.

Jzzhu doesn't want to waste the money of the country, so he is going to close some of the train routes. Please tell Jzzhu the maximum number of the train routes which can be closed under the following condition: the length of the shortest path from every city to the capital mustn't change.

Jzzhu 是 A 国的总统。他的国家中有 $n$ 座城市，编号从 $1$ 到 $n$。其中城市 $1$ 是 A 国的首都。此外，有 $m$ 条道路连接这些城市。通过第 $i$ 条道路，可以从城市 $u_i$ 到达城市 $v_i$（反之亦然），该道路的长度为 $x_i$。最后，国内还有 $k$ 条铁路线路。通过第 $i$ 条铁路线路，可以从首都到达城市 $s_i$（反之亦然），该线路的长度为 $y_i$。

Jzzhu 不想浪费国家的资金，因此他打算关闭部分铁路线路。请告诉 Jzzhu：在满足如下条件的前提下，最多可以关闭多少条铁路线路？即：每座城市到首都的最短路径长度不得改变。

The first line contains three integers n, m, k (2 ≤ n ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105).

Each of the next m lines contains three integers u__i, v__i, x__i (1 ≤ u__i, v__i ≤ n; u__i ≠ v__i; 1 ≤ x__i ≤ 109).

Each of the next k lines contains two integers s__i and y__i (2 ≤ s__i ≤ n; 1 ≤ y__i ≤ 109).

It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital.

第一行包含三个整数 $n$、$m$、$k$（$2 \leq n \leq 10^5$；$1 \leq m \leq 3 \cdot 10^5$；$1 \leq k \leq 10^5$）。

接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$、$x_i$（$1 \leq u_i, v_i \leq n$；$u_i \neq v_i$；$1 \leq x_i \leq 10^9$）。

接下来的 $k$ 行，每行包含两个整数 $s_i$ 和 $y_i$（$2 \leq s_i \leq n$；$1 \leq y_i \leq 10^9$）。

保证从每个城市到首都至少存在一条路径。注意，两座城市之间可能存在多条道路；同样，从首都到同一座城市的路径也可能有多条。

Output a single integer representing the maximum number of the train routes which can be closed.

输出一个整数，表示最多可以关闭的火车线路数量。