题目描述

$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}$ が互いに友達であることをさす。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ を空白区切りで一行に出力せよ。

题目大意

给 $N$ 个点，$M$ 条边，每个点的颜色（值域为 $[1,K]$）。并给定 $L$ 个点作为特殊点。

询问 每个点到最近的与其颜色不同的特殊点的距离（无解输出 -1） 。

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

3 1 3 1
1 2 3
1
1 2 1000000000

-1 1000000000 -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\ <\ 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)$
• 入力は全て整数である。

Sample Explanation 1

人 $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$ となります。

Sample Explanation 2

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