AT_abc245_g [ABC245G] Foreign Friends

[problemUrl]: https://atcoder.jp/contests/abc245/tasks/abc245_g $ 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 $ $ 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 $ を空白区切りで一行に出力せよ。

### 制約 - $ 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\