外国朋友

题目描述

有 $N$ 个人和 $K$ 个国家,分别编号为 Person $1$,Person $2$,$\ldots$,Person $N$ 和 Nation $1$,Nation $2$,$\ldots$,Nation $K$。

每个人恰好属于一个国家:Person $i$ 属于 Nation $A_i$。

此外,其中有 $L$ 位名人:Person $B_1$,Person $B_2$,$\ldots$,Person $B_L$ 是名人。

最初,这 $N$ 个人之间没有朋友关系。

对于 $M$ 对人,Takahashi 作为神,可以支付一定代价让他们成为朋友:对每个 $1\le i\le M$,他可以支付 $C_i$ 的代价,使 Person $U_i$ 和 Person $V_i$ 成为朋友。

现在,对每个 $1\le i\le N$,求解下面的问题。

Takahashi 能否让 Person $i$ 与「属于不同于 Person $i$ 所在国家的名人」成为间接朋友?如果能,求所需的最小总代价。

这里,当存在非负整数 $n$ 和人的序列 $(u_0,u_1,\ldots,u_n)$,满足 $u_0=s$,$u_n=t$,且对每个 $0\le i\lt n$,Person $u_i$ 和 Person $u_{i+1}$ 是朋友时,称 Person $s$ 是 Person $t$ 的间接朋友。

输入格式

输入按以下格式从标准输入给出:

N M K L
A_1 A_2 … A_N
B_1 B_2 … B_L
U_1 V_1 C_1
U_2 V_2 C_2
⋮
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$ 和 $2$ 成为朋友,再支付 $30$ 让 Person $2$ 和 $3$ 成为朋友,合计 $15+30=45$。
• 对 Person $2$,属于不同国家的名人只有 Person $3$。支付 $30$ 让 Person $2$ 和 $3$ 成为朋友,即可达到最小代价。
• 对 Person $3$,属于不同国家的名人只有 Person $2$。支付 $30$ 让 Person $2$ 和 $3$ 成为朋友,即可达到最小代价。
• 对 Person $4$,属于不同国家的名人只有 Person $2$。以最小代价让他们成为间接朋友,应支付 $15$ 让 Person $1$ 和 $2$ 成为朋友,再支付 $10$ 让 Person $1$ 和 $4$ 成为朋友,合计 $15+10=25$。

3 1 3 1
1 2 3
1
1 2 1000000000

-1 1000000000 -1

注意,对 Person $1$ 来说,Person $1$ 本身确实是间接朋友,但它与 Person $1$ 属于同一个国家,所以不存在属于不同国家的名人。

数据范围

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