问题描述

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

约束条件

• $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$
• 所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

$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

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

示例输出 1

0
1
1
2

感染情况如下：

• 第 $0$ 天晚上，住在房间 $1$ 中的人被感染。
• 房间 $1$ 和房间 $2,3,4$ 之间的距离分别为 $2,3,5$。因此，由于 $X_1=3$，住在房间 $2$ 和 $3$ 的人在第 $1$ 天晚上被新感染。
• 房间 $3$ 和房间 $4$ 之间的距离为 $2$。因此，由于 $X_2=3$，住在房间 $4$ 的人也在第 $2$ 天晚上被感染。

因此，住在房间 $1,2,3,4$ 的人在第 $0,1,1,2$ 天分别被新感染，所以按照这个顺序分别打印 $0,1,1,2$。

示例输入 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

示例输出 2

0
1
2
-1
2
0
-1

示例输入 3

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

示例输出 3

0
2
0
-1
-1

注意，并不总是可以只使用走廊在任意两个房间之间移动。