AT_past202104_g 一日一歩

在一个国家有 $n$ 个城市（编号从 $1$ 到 $n$）和 $m$ 条公路（编号从 $1$ 到 $m$）。其中，第 $i$ 条道路连接城市 $a_i$ 与城市 $b_i$，需要花费 $c_i$ 单位时间通过。 现在的你来到了这个国家。你位于城市 $1$。你决定从第二天早上开始，在 $q$ 天里环游这个国家。每天早上，你都会决定进行下面两种行动中的任意一种： - 什么都不做； - 选择一条与当前城市相连的公路，并驾车前往这条公路通往的城市。此时，若选择的道路通行时间不大于 $x_i$，你才可以走这条公路。 对于满足 $1 \le i \le q$ 的所有整数 $i$，请你按顺序求出你能在第 $i$ 天傍晚到达几个城市？（注：$1$ 单位时间 $\le$ 一天的 $\frac{1}{10^{100}}$）

输入由以下格式由标准输入读入： >$n$ $m$ $q$ > >$a_1$ $b_1$ $c_1$ > >$a_2$ $b_2$ $c_2$ > >... > >$a_m$ $b_m$ $c_m$ > >$x_1$ $x_2$ ... $x_q$

输出共 $q$ 行，每行一个正整数，第 $i$ 行输出第 $i$ 天傍晚可到达的城市个数。

#### 输入输出样例 #1 说明 在第 $1$ 天早上，你不能走任意一条道路，所以 $ans_1=1$。 在第 $2$ 天早上，你可以走 $2$ 号公路到达城市 $3$，或者留在城市 $1$，所以 $ans_2=2$。 在第 $3$ 天早上，（如果你在与那条路相连的城市）你可以使用 $2,3$ 号公路，如果前一天到了城市 $3$，那么可以在今天到达城市 $2$。所以 $ans_3=3$。 在第 $4$ 天早上，所有公路均可通行，但你能到达的城市也只有 $1,2,3$ 三个，所以答案依然为 $3$。 #### 输入输出样例 #2 说明 请注意，一天只能走一条公路。 #### 输入输出样例 #3 说明 请注意，可能会有无法通过道路到达的城市。 #### 数据规模与约定 对于全部的测试点，数据保证： - $2 \le n \le 2 \times 10^5$，$1 \le m,q \le 2 \times 10^5$； - $1 \le a_i \lt b_i \le n$，且任意两对 $(a_i,b_i)$ 都是不同的； - $1 \le c_i,x_i \le 10^9$； - 输入中的所有值均为整数。