G - 外国朋友

分数：$600$ 分

问题描述

有 $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$ 成为与人 $i$ 所属国家不同的受欢迎的人的间接朋友？如果可以，求所需总成本的最小值。这里，当存在一个非负整数 $n$ 和一个人的序列 $(u_0, u_1, \ldots, u_n)$ ，使得 $u_0=s$ ， $u_n=t$ ，以及人 $u_i$ 和人 $u_{i+1}$ 是每个 $0\leq i < n$ 的朋友时，称人 $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$
• 如果 $i \neq j$，有 $(U_i, V_i)\neq (U_j,V_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$ 定义如下：如果不可能使 Person $i$ 成为不属于 Person $i$ 国家的受欢迎的人的间接朋友，则 $X_i = -1$；否则，$X_i$ 是所需的最小总代价。 在一行中输出 $X_1, X_2, \ldots, X_N$，用空格分隔。

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

45 30 30 25

Person $1$, $2$, $3$, $4$ 属于 Nation $1$, $1$, $2$, $2$，其中有两个受欢迎的人：Person $2$ 和 $3$。这里：

• 对于 Person $1$，属于不同国家且是受欢迎的人的唯一一个是 Person $3$。要以最小代价使其成为间接朋友，我们需要支付代价 $15$ 使 Person $1$ 和 Person $2$ 成为朋友，并支付代价 $30$ 使 Person $2$ 和 Person $3$ 成为朋友，总共代价为 $15+30=45$。
• 对于 Person $2$，属于不同国家且是受欢迎的人的唯一一个是 Person $3$。最小代价实现通过支付代价 $30$ 使 Person $2$ 和 Person $3$ 成为朋友。
• 对于 Person $3$，属于不同国家且是受欢迎的人的唯一一个是 Person $2$。最小代价实现通过支付代价 $30$ 使 Person $2$ 和 Person $3$ 成为朋友。
• 对于 Person $4$，属于不同国家且是受欢迎的人的唯一一个是 Person $2$。要以最小代价使其成为间接朋友，我们需要支付代价 $15$ 使 Person $1$ 和 Person $2$ 成为朋友，并支付代价 $10$ 使 Person $1$ 和 Person $4$ 成为朋友，总共代价为 $15+10=25$。

3 1 3 1
1 2 3
1
1 2 1000000000

-1 1000000000 -1

请注意，对于 Person $1$，Person $1$ 本身的确是间接朋友，但它不属于不同国家，所以没有属于不同国家的受欢迎的人。