CF449B Jzzhu and Cities

Jzzhu 是国家 A 的总统。在他的国家里有 $n$ 个城市，编号从 $1$ 到 $n$。城市 $1$ 是国家 A 的首都。还有 $m$ 条道路连接这些城市。可以通过第 $i$ 条道路从城市 $u_i$ 到 $v_i$（反之亦然），这条路的长度为 $x_i$。最后，国家里有 $k$ 条火车线路。每一条第 $i$ 条火车线路可以从国家的首都到达城市 $s_i$（反之亦然），这条线路的长度为 $y_i$。 Jzzhu 不希望浪费国家的钱，所以他准备关闭部分火车线路。请告诉 Jzzhu，在下述条件下最多能关闭多少条火车线路：从每个城市到首都的最短路长度必须保持不变。

第一行包含三个整数 $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 \ne 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$。 保证每个城市到首都至少有一条路径可以到达。注意，两个城市之间可以有多条道路，也可以有多条火车线路通往同一个城市。

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

由 ChatGPT 5 翻译