102456: [AtCoder]ABC245 G - Foreign Friends

Problem Statement

There are $N$ people and $K$ nations, labeled as Person $1$, Person $2$, $\ldots$, Person $N$ and Nation $1$, Nation $2$, $\ldots$, Nation $K$, respectively.
Each person belongs to exactly one nation: Person $i$ belongs to Nation $A_i$. Additionally, there are $L$ popular people among them: Person $B_1$, Person $B_2$, $\ldots$, Person $B_L$ are popular. Initially, no two of the $N$ people are friends.

For $M$ pairs of people, Takahashi, a God, can make them friends by paying a certain cost: for each $1\leq i\leq M$, he can pay the cost of $C_i$ to make Person $U_i$ and Person $V_i$ friends.

Now, for each $1\leq i\leq N$, solve the following problem.

Can Takahashi make Person $i$ an indirect friend of a popular person belonging to a nation different from that of Person $i$? If he can do so, find the minimum total cost needed. Here, Person $s$ is said to be an indirect friend of Person $t$ when there exists a non-negative integer $n$ and a sequence of people $(u_0, u_1, \ldots, u_n)$ such that $u_0=s$, $u_n=t$, and Person $u_i$ and Person $u_{i+1}$ are friends for each $0\leq i < n$.

Constraints

• $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$
• $(U_i, V_i)\neq (U_j,V_j)$ if $i \neq j$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Output

Let $X_i$ defined as follows: $X_i$ is $-1$ if it is impossible to make Person $i$ an indirect friend of a popular person belonging to a nation different from that of Person $i$; otherwise, $X_i$ is the minimum total cost needed to do so. Print $X_1, X_2, \ldots, X_N$ in one line, with spaces in between.

Sample Input 1

4 4 2 2
1 1 2 2
2 3
1 2 15
2 3 30
3 4 40
1 4 10

Sample Output 1

45 30 30 25

Person $1$, $2$, $3$, $4$ belong to Nation $1$, $1$, $2$, $2$, respectively, and there are two popular people: Person $2$ and $3$. Here,

• For Person $1$, the only popular person belonging to a different nation is Person $3$. To make them indirect friends with the minimum cost, we should pay the cost of $15$ to make Person $1$ and $2$ friends and pay $30$ to make Person $2$ and $3$ friends, for a total of $15+30=45$.
• For Person $2$, the only popular person belonging to a different nation is Person $3$. The minimum cost is achieved by making Person $2$ and $3$ friends by paying $30$.
• For Person $3$, the only popular person belonging to a different nation is Person $2$. The minimum cost is achieved by making Person $2$ and $3$ friends by paying $30$.
• For Person $4$, the only popular person belonging to a different nation is Person $2$. To make them indirect friends with the minimum cost, we should pay the cost of $15$ to make Person $1$ and $2$ friends and pay $10$ to make Person $1$ and $4$ friends, for a total of $15+10=25$.

Sample Input 2

3 1 3 1
1 2 3
1
1 2 1000000000

Sample Output 2

-1 1000000000 -1

Note that, for Person $1$, Person $1$ itself is indeed an indirect friend, but it does not belong to a different nation, so there is no popular person belonging to a different nation.

问题描述

有$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\leq i\leq M$，他可以支付成本$C_i$使Person $U_i$和Person $V_i$成为朋友。

现在，对于每个$1\leq i\leq N$，解决以下问题。

Takahashi能让Person $i$成为来自与Person $i$所属国家不同的名人的间接朋友吗？ 如果可以，找到所需最低总成本。 这里，当存在一个非负整数$n$和一个由人组成的序列$(u_0, u_1, \ldots, u_n)$ 使得$u_0=s$，$u_n=t$，并且Person $u_i$和Person $u_{i+1}$是朋友时，称Person $s$是Person $t$的间接朋友，对于每个$0\leq i < 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$
• $(U_i, V_i)\neq (U_j,V_j)$如果$i \neq 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$如下：如果无法使Person $i$成为来自与Person $i$所属国家不同的名人的间接朋友，则$X_i$为$-1$；否则，$X_i$是所需的最低总成本。 在一行中输出$X_1, X_2, \ldots, X_N$，之间用空格分隔。

样例输入1

4 4 2 2
1 1 2 2
2 3
1 2 15
2 3 30
3 4 40
1 4 10

样例输出1

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$。

样例输入2

3 1 3 1
1 2 3
1
1 2 1000000000

样例输出2

-1 1000000000 -1

注意，对于Person $1$，Person $1$本身确实是一个间接朋友，但它不属于一个不同的国家，因此没有来自不同国家的名人。