病毒扩散 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$ 时,才会被新感染。

这里,房间 $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$ 的人被新感染的日期。

样例

4 4
1 2 2
2 3 1
2 4 3
3 4 2
1
1
2
3 3

0
1
1
2

感染的传播过程如下。

第 $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$。

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

0
1
2
-1
2
0
-1

5 1
1 2 5
2
1 3
3
3 7 5

0
2
0
-1
-1

注意,并不一定总能仅使用走廊在任意两个房间之间移动。

数据范围

• $1 \le N \le 3\times 10^5$
• $0 \le M \le 3\times 10^5$
• $1 \le U_i \lt V_i \le N$
• 所有 $(U_i,V_i)$ 互不相同
• $1 \le W_i \le 10^9$
• $1 \le K \le N$
• $1 \le A_1 \lt A_2 \lt \cdots \lt A_K \le N$
• $1 \le D \le 3\times 10^5$
• $1 \le X_i \le 10^9$
• 输入中的所有值均为整数