AT_abc307_f [ABC307F] Virus 2

有 $N$ 个房间，编号为 $1, 2, \ldots, N$，每个房间里住着一人。此外，有 $M$ 条通道连接着一些不同的两个房间。第 $i$ 条通道连接房间 $U_i$ 和房间 $V_i$，长度为 $W_i$。 某一天（记为第 $0$ 天夜晚），住在房间 $A_1, A_2, \ldots, A_K$ 的 $K$ 个人被新感染了病毒。接下来的 $D$ 天里，第 $i$ 天（$1 \leq i \leq D$）病毒的传播方式如下： > 在第 $(i-1)$ 天夜晚已经感染的人，在第 $i$ 天夜晚依然保持感染状态。 > 对于其他人，如果他们住的房间与第 $(i-1)$ 天夜晚已感染者所住的任意一个房间之间的距离不超过 $X_i$，则在第 $i$ 天夜晚新感染。这里，房间 $P$ 和房间 $Q$ 之间的距离定义为仅通过通道从 $P$ 到 $Q$ 时所经过通道长度的最小总和。如果无法仅通过通道从 $P$ 到 $Q$ 移动，则距离视为 $10^{100}$。 请对于每个 $i$（$1 \leq i \leq N$），输出住在房间 $i$ 的人是在第几天夜晚新感染的。如果到第 $D$ 天夜晚仍未感染，则输出 $-1$。

输入按以下格式从标准输入给出。 > $N$ $M$ > $U_1$ $V_1$ $W_1$ > $U_2$ $V_2$ $W_2$ > $\vdots$ > $U_M$ $V_M$ $W_M$ > $K$ > $A_1$ $A_2$ $\ldots$ $A_K$ > $D$ > $X_1$ $X_2$ $\ldots$ $X_D$

输出 $N$ 行。 第 $i$ 行（$1 \leq i \leq N$）输出住在房间 $i$ 的人是在第几天夜晚新感染的。

### 约束条件 - $1 \leq N \leq 3 \times 10^5$ - $0 \leq M \leq 3 \times 10^5$ - $1 \leq U_i < V_i \leq N$ - 所有 $(U_i, V_i)$ 均不同 - $1 \leq W_i \leq 10^9$ - $1 \leq K \leq N$ - $1 \leq A_1 < A_2 < \cdots < A_K \leq N$ - $1 \leq D \leq 3 \times 10^5$ - $1 \leq X_i \leq 10^9$ - 所有输入均为整数 ### 样例解释 1 病毒的传播过程如下： - 第 $0$ 天夜晚，住在房间 $1$ 的人感染。 - 房间 $1$ 到房间 $2,3,4$ 的距离分别为 $2,3,5$。由于 $X_1=3$，所以第 $1$ 天夜晚，住在房间 $2,3$ 的人新感染。 - 房间 $3$ 到房间 $4$ 的距离为 $2$。由于 $X_2=3$，所以第 $2$ 天夜晚，住在房间 $4$ 的人也感染。 因此，住在房间 $1,2,3,4$ 的人分别在第 $0,1,1,2$ 天新感染，按顺序输出 $0,1,1,2$。 ### 样例解释 3 请注意，并非所有两个房间之间都一定可以仅通过通道互相到达。 由 ChatGPT 4.1 翻译