Problem Description

In a certain country, there are cities numbered from $1$ to $N$ and roads numbered from $1$ to $M$.
Road $i$ connects city $A_i$ and city $B_i$ bidirectionally and can be traversed in $C_i$ units of time.
You are currently in city $1$ and plan to travel for $Q$ days. On the $i$-th day of the trip, you will perform one of the following actions during the day:

• Do nothing
• Choose one road connected to the city you are currently in and move to the city at the other end of that road. The chosen road must be traversable in $X_i$ units of time or less.

For each integer $i$ from $1$ to $Q$, determine the number of cities you could potentially be in at the end of the $i$-th day.
Assume that $1$ unit of time is shorter than $\frac{1}{10^{100}}$ of a day.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ A_3 $ $ B_3 $ $ C_3 $ $\hspace{25pt}\ \vdots$ $ A_M $ $ B_M $ $ C_M $ $ X_1 $ $ X_2 $ $ X_3 $ $\dots$ $ X_Q $

Output Format

Output $Q$ lines. The $i$-th line should contain the number of cities you could potentially be in at the end of the $i$-th day.

Sample Input and Output

Sample Input #1

3 3 4
1 2 7
1 3 3
2 3 5
2 4 6 8

Sample Output #1

1
2
3
3

Sample Input #2

5 7 5
1 2 6
2 3 4
1 3 3
1 4 1
3 4 6
3 5 5
1 5 9
1 5 4 3 5

Sample Output #2

2
3
4
4
5

Sample Input #3

4 1 3
1 4 100
50 100 1000000000

Sample Output #3

1
2
2

Notes/Hints

Constraints

• $2\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ M\ \le\ 2\ \times\ 10^5$
• $1\ \le\ Q\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ <\ B_i\ \le\ N$
• $i\ \neq\ j$ implies $(A_i,\ B_i)\ \neq\ (A_j,\ B_j)$
• $1\ \le\ C_i\ \le\ 10^9$
• $1\ \le\ X_i\ \le\ 10^9$
• All values in the input are integers

Sample Explanation 1

• On the 1st day, there are no roads connected to city $1$ that can be traversed in $2$ units of time or less, so you stay in city $1$. The possible city at the end of the day is city $1$.
• On the 2nd day, only road $2$ can be used, allowing you to move to city $3$ or stay in city $1$. The possible cities at the end of the day are cities $1$ and $3$.
• On the 3rd day, roads $2$ and $3$ can be used. If you were in city $3$ the previous day, you can move to city $2$ using road $3$. The possible cities at the end of the day are cities $1$, $2$, and $3$.
• On the 4th day, all roads can be used, but the possible cities at the end of the day remain cities $1$, $2$, and $3$.

Sample Explanation 2

Note that you cannot use multiple roads in one day.

Sample Explanation 3

There might be cities that cannot be reached using the roads.

见题面 Input 部分

见题面 Output 部分