AT_codequeen2024_final_d Attend Many Events

AtCoder Land 有 $N$ 个地点和 $M$ 条道路。第 $i$ 条道路连接地点 $a_i$ 和 $b_i$（双向），通过它需要花费 $d_i$ 分钟。 接下来，AtCoder Land 会举办 $K$ 个活动。要参加第 $i$ 个活动，必须在时间 $t_i$ 分钟时到达地点 $c_i$。每个活动所需时间为 $0$ 分钟。 你目前在时间 $0$ 分钟时位于地点 $1$。请你求出在合理规划路线的情况下，最多能参加多少个活动。

输入通过标准输入按以下格式给出。 > $N$ $M$ $K$ > $a_1$ $b_1$ $d_1$ > $a_2$ $b_2$ $d_2$ > $\vdots$ > $a_M$ $b_M$ $d_M$ > $c_1$ $t_1$ > $c_2$ $t_2$ > $\vdots$ > $c_K$ $t_K$

输出答案。

### 样例解释 1 比如，按照如下路线行动，可以参加 $2$ 个活动。 - 起始时刻，$0$ 分钟，在地点 $1$。 - 通过道路 $1$，在 $1$ 分钟时到达地点 $2$。 - $2$ 分钟时，在地点 $2$ 参加活动 $2$。 - 通过道路 $1$，在 $3$ 分钟时返回地点 $1$。 - 通过道路 $2$，在 $6$ 分钟时到达地点 $3$。 - $7$ 分钟时，在地点 $3$ 参加活动 $3$。 无法参加超过 $3$ 个活动，因此答案为 $2$。 ### 样例解释 2 由于没有道路，无法离开地点 $1$，但可以参加在地点 $1$ 举办的两个活动。 ### 数据范围 - $1 \leq N \leq 1000$ - $0 \leq M \leq 1000$ - $1 \leq K \leq 1000$ - $1 \leq a_i < b_i \leq N$ - 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ - $1 \leq d_i \leq 10^9$ - $1 \leq c_i \leq N$ - $1 \leq t_i \leq 10^9$ - 若 $i \neq j$，则 $(c_i,t_i) \neq (c_j,t_j)$ - 所有输入均为整数。 由 ChatGPT 5 翻译