问题陈述

有 $N$ 个人和 $K$ 个国家，分别标记为第 $1$ 个人、第 $2$ 个人，$\\ldots$，第 $N$ 个人和第 $1$ 个国家、第 $2$ 个国家，$\\ldots$，第 $K$ 个国家。
每个人属于且仅属于一个国家：第 $i$ 个人属于国家 $A_i$。此外，其中有 $L$ 个受欢迎的人：第 $B_1$ 个人、第 $B_2$ 个人，$\\ldots$，第 $B_L$ 个人是受欢迎的。初始时，这 $N$ 个人中没有两个人是朋友。

对于 $M$ 对人，作为一个神，高桥可以支付一定的费用将他们变成朋友：对于每个 $1\\leq i\\leq M$，他可以支付费用 $C_i$ 将第 $U_i$ 个人和第 $V_i$ 个人变成朋友。

现在，对于每个 $1\\leq i\\leq N$，解决以下问题。

高桥是否能使第 $i$ 个人成为一个与他国家不同的受欢迎的人的间接朋友？如果可以，找到所需的最小总费用。这里，当存在非负整数 $n$ 和一个人序列 $(u_0, u_1, \\ldots, u_n)$ 使得 $u_0=s$，$u_n=t$，并且对于每个 $0\\leq i < n$，第 $u_i$ 个人和第 $u_{i+1}$ 个人是朋友时，人 $s$ 被称为人 $t$ 的间接朋友。

约束条件

• $2 \\leq N \\leq 10^5$
• $1 \\leq M \\leq 10^5$
• $1 \\leq K \\leq 10^5$
• $1 \\leq L \\leq N$
• $1 \\leq A_i \\leq K$
• $1 \\leq B_1<B_2<\\cdots<B_L\\leq N$
• $1\\leq C_i\\leq 10^9$
• $1\\leq U_i<V_i\\leq N$
• $(U_i, V_i)\\neq (U_j,V_j)$ if $i \\neq j$.
• 输入中的所有值均为整数。

输入

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

$N$ $M$ $K$ $L$ $A_1$ $A_2$ $\\cdots$ $A_N$ $B_1$ $B_2$ $\\cdots$ $B_L$ $U_1$ $V_1$ $C_1$ $U_2$ $V_2$ $C_2$ $\\vdots$ $U_M$ $V_M$ $C_M$

输出

定义 $X_i$ 如下：如果无法使第 $i$ 个人成为与他国家不同的受欢迎的人的间接朋友，则 $X_i$ 等于 $\-1$；否则，$X_i$ 是使其成为间接朋友所需的最小总费用。以一行输出 $X_1, X_2, \\ldots, X_N$，中间用空格分隔。

示例输入 1

4 4 2 2
1 1 2 2
2 3
1 2 15
2 3 30
3 4 40
1 4 10

示例输出 1

45 30 30 25

第 $1$ 个人、第 $2$ 个人、第 $3$ 个人、第 $4$ 个人属于国家 $1$、$1$、$2$、$2$，其中有两个受欢迎的人：第 $2$ 个人和第 $3$ 个人。在这里，

• 对于第 $1$ 个人，与他国家不同的唯一一个受欢迎的人是第 $3$ 个人。为了以最小的费用使他们成为间接朋友，我们应该支付费用 $15$ 使第 $1$ 个人和第 $2$ 个人成为朋友，并支付 $30$ 使第 $2$ 个人和第 $3$ 个人成为朋友，总共 $15+30=45$。
• 对于第 $2$ 个人，与他国家不同的唯一一个受欢迎的人是第 $3$ 个人。通过支付 $30$ 使第 $2$ 个人和第 $3$ 个人成为朋友可以达到最小费用。
• 对于第 $3$ 个人，与他国家不同的唯一一个受欢迎的人是第 $2$ 个人。通过支付 $30$ 使第 $2$ 个人和第 $3$ 个人成为朋友可以达到最小费用。
• 对于第 $4$ 个人，与他国家不同的唯一一个受欢迎的人是第 $2$ 个人。为了以最小的费用使他们成为间接朋友，我们应该支付费用 $15$ 使第 $1$ 个人和第 $2$ 个人成为朋友，并支付 $10$ 使第 $1$ 个人和第 $4$ 个人成为朋友，总共 $15+10=25$。

示例输入 2

3 1 3 1
1 2 3
1
1 2 1000000000

示例输出 2

-1 1000000000 -1

请注意，对于第 $1$ 个人，第 $1$ 个人本身确实是一个间接朋友，但它不属于一个不同的国家，因此没有属于不同国家的受欢迎的人。