AT_abc245_g [ABC245G] Foreign Friends

有 $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$ 与一个属于不同国家的“人气者”间接成为朋友？如果可以，请求出达成这一目标所需的最小总费用。这里，若存在某个非负整数 $n$ 和一列人 $(u_0, u_1, \ldots, u_n)$，满足 $u_0=s$，$u_n=t$，且对于所有 $0\leq i < n$，人 $u_i$ 和人 $u_{i+1}$ 是朋友，则称人 $s$ 和人 $t$ 间接为朋友。

输入按以下格式从标准输入给出。 > $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$ 与属于不同国家的“人气者”间接成为朋友所需的最小费用。如果无法达成，则 $X_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 < 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)$ - 所有输入均为整数。 ### 样例解释 1 人 $1$、人 $2$、人 $3$、人 $4$ 分别属于国家 $1$、国家 $1$、国家 $2$、国家 $2$，人气者为人 $2$、人 $3$ 共 $2$ 人。此时： - 对于人 $1$，属于不同国家的人气者只有人 $3$。让人 $1$ 与人 $3$ 间接成为朋友的最小费用为 $15+30=45$（即先支付 $15$ 让人 $1$ 与人 $2$ 成为朋友，再支付 $30$ 让人 $2$ 与人 $3$ 成为朋友）。 - 对于人 $2$，属于不同国家的人气者只有人 $3$。直接支付 $30$ 让人 $2$ 与人 $3$ 成为朋友，费用最小。 - 对于人 $3$，属于不同国家的人气者只有人 $2$。直接支付 $30$ 让人 $2$ 与人 $3$ 成为朋友，费用最小。 - 对于人 $4$，属于不同国家的人气者只有人 $2$。让人 $4$ 与人 $2$ 间接成为朋友的最小费用为 $10+15=25$（即先支付 $10$ 让人 $1$ 与人 $4$ 成为朋友，再支付 $15$ 让人 $1$ 与人 $2$ 成为朋友）。 ### 样例解释 2 对于人 $1$，虽然自己可以算作间接朋友，但由于没有属于不同国家的人气者，故不存在满足条件的对象。请注意“属于不同国家的人气者”的条件。 由 ChatGPT 4.1 翻译