配点 : $600$ 点

問題文

$N$ 人の人と $K$ 個の国があり、それぞれ 人 $1$, 人 $2$, $\ldots$, 人 $N$ および国 $1$, 国 $2$, $\ldots$, 国 $K$ と番号が付いています。 それぞれの人はちょうど $1$ つの国に属しており、人 $i$ は国 $A_i$ に属しています。 また、$L$ 人の人気者がおり、具体的には人 $B_1$, 人 $B_2$, $\ldots$, 人 $B_L$ が人気者です。 最初、$N$ 人のうちどの $2$ 人も友達ではありません。

神様である高橋君は、$M$ 個の $2$ 人組のペアについて、コストを支払うことで互いに友達にすることができます。 具体的には $1\leq i\leq M$ について、コスト $C_i$ を支払うことで人 $U_i$ と人 $V_i$ を互いに友達にすることができます。

ここで、各 $1\leq i\leq N$ について、次の問題を解いてください。

高橋君は、人 $i$ を、人 $i$ の属する国とは異なる国に属する人気者と間接的に友達にすることは可能か？ 可能ならば、それを達成するのに必要なコストの総和の最小値を求めよ。 ただし、人 $s$ と人 $t$ が間接的に友達であるとは、ある非負整数 $n$ と人の列 $(u_0, u_1, \ldots , u_n)$ が存在し, $u_0=s$, $u_n=t$ かつ $0\leq i < n$ について、人 $u_i$ と 人 $u_{i+1}$ が互いに友達であることをさす。

制約

• $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
• $1\leq C_i\leq 10^9$
• $1\leq U_i
• $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$ を、人 $i$ を異なる国に属する人気者と間接的に友達にすることが不可能ならば $-1$、 そうでないならば、達成するのに必要な最小コストの値として定義する。 $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

人 $1$, 人 $2$, 人 $3$, 人 $4$ はそれぞれ国 $1$, 国 $1$, 国 $2$, 国 $2$ に属しており、人気者は人 $2$, 人 $3$ の $2$ 名です。このとき、

• 人 $1$ と異なる国に属する人気者は人 $3$ のみです。人 $1$ と 人 $3$ を間接的に友達にするには、それぞれコスト $15,30$ を払って人 $1$ と人 $2$, 人 $2$ と人 $3$ を友達にした時がかかるコストが最小で、このとき $15+30=45$ となります。
• 人 $2$ と異なる国に属する人気者は人 $3$ のみです。コスト $30$ を払って人 $2$ と人 $3$ を友達にした時が最小となります。
• 人 $3$ と異なる国に属する人気者は人 $2$ のみです。コスト $30$ を払って人 $2$ と人 $3$ を友達にした時が最小となります。
• 人 $4$ と異なる国に属する人気者は人 $2$ のみです。人 $4$ と 人 $2$ を間接的に友達にするには、それぞれコスト $15,10$ を払って人 $1$ と人 $2$, 人 $1$ と人 $4$ を友達にした時がかかるコストが最小で、このとき $15+10=25$ となります。

3 1 3 1
1 2 3
1
1 2 1000000000

-1 1000000000 -1

人 $1$ にとって自身は間接的な友達といえますが、異なる国に属していないため、 「異なる国に属する人気者」の条件をみたす相手はいないことに注意してください。