CF1389G.Directing Edges

You are given an undirected connected graph consisting of $n$ vertices and $m$ edges. $k$ vertices of this graph are special.

You have to direct each edge of this graph or leave it undirected. If you leave the $i$-th edge undirected, you pay $w_i$ coins, and if you direct it, you don't have to pay for it.

Let's call a vertex saturated if it is reachable from each special vertex along the edges of the graph (if an edge is undirected, it can be traversed in both directions). After you direct the edges of the graph (possibly leaving some of them undirected), you receive $c_i$ coins for each saturated vertex $i$. Thus, your total profit can be calculated as $\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$, where $S$ is the set of saturated vertices, and $U$ is the set of edges you leave undirected.

For each vertex $i$, calculate the maximum possible profit you can get if you have to make the vertex $i$ saturated.

你被给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通图。该图中有 $k$ 个顶点是特殊的。

你需要为图中的每条边指定一个方向，或保持其无向。若将第 $i$ 条边保持无向，则需支付 $w_i$ 枚金币；若为其指定方向，则无需为此边付费。

我们称一个顶点是饱和的（saturated），当且仅当它可以从每个特殊顶点出发，沿着图中的边（若某边保持无向，则可双向通行）到达。在你为图的边定向（可能保留其中一些边为无向）之后，对每个饱和顶点 $i$，你将获得 $c_i$ 枚金币。因此，你的总收益可计算为 $\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$，其中 $S$ 是饱和顶点的集合，$U$ 是你保留为无向的边的集合。

对每个顶点 $i$，请计算：在强制要求顶点 $i$ 必须为饱和顶点的前提下，你能获得的最大可能收益。

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 3 \cdot 10^5$, $n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2})$, $1 \le k \le n$).

The second line contains $k$ pairwise distinct integers $v_1$, $v_2$, ..., $v_k$ ($1 \le v_i \le n$) — the indices of the special vertices.

The third line contains $n$ integers $c_1$, $c_2$, ..., $c_n$ ($0 \le c_i \le 10^9$).

The fourth line contains $m$ integers $w_1$, $w_2$, ..., $w_m$ ($0 \le w_i \le 10^9$).

Then $m$ lines follow, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) — the endpoints of the $i$-th edge.

There is at most one edge between each pair of vertices.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 3 \cdot 10^5$，$n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2})$，$1 \le k \le n$）。

第二行包含 $k$ 个两两不同的整数 $v_1$、$v_2$、…、$v_k$（$1 \le v_i \le n$）—— 特殊顶点的编号。

第三行包含 $n$ 个整数 $c_1$、$c_2$、…、$c_n$（$0 \le c_i \le 10^9$）。

第四行包含 $m$ 个整数 $w_1$、$w_2$、…、$w_m$（$0 \le w_i \le 10^9$）。

接下来是 $m$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$）—— 第 $i$ 条边的两个端点。

任意一对顶点之间至多存在一条边。

Print $n$ integers, where the $i$-th integer is the maximum profit you can get if you have to make the vertex $i$ saturated.

输出 $n$ 个整数，其中第 $i$ 个整数表示：若必须使顶点 $i$ 达到饱和状态，你能获得的最大利润。

Consider the first example:

• the best way to make vertex $1$ saturated is to direct the edges as $2 \to 1$, $3 \to 2$; $1$ is the only saturated vertex, so the answer is $11$;
• the best way to make vertex $2$ saturated is to leave the edge $1-2$ undirected and direct the other edge as $3 \to 2$; $1$ and $2$ are the saturated vertices, and the cost to leave the edge $1-2$ undirected is $10$, so the answer is $2$;
• the best way to make vertex $3$ saturated is to direct the edges as $2 \to 3$, $1 \to 2$; $3$ is the only saturated vertex, so the answer is $5$.

The best course of action in the second example is to direct the edges along the cycle: $1 \to 2$, $2 \to 3$, $3 \to 4$ and $4 \to 1$. That way, all vertices are saturated.

考虑第一个例子：

• 使顶点 $1$ 达到饱和的最优方式是将边定向为 $2 \to 1$、$3 \to 2$；此时仅顶点 $1$ 是饱和的，因此答案为 $11$；
• 使顶点 $2$ 达到饱和的最优方式是保持边 $1\text{-}2$ 无向，并将另一条边定向为 $3 \to 2$；此时顶点 $1$ 和 $2$ 均为饱和顶点，而保持边 $1\text{-}2$ 无向的代价为 $10$，因此答案为 $2$；
• 使顶点 $3$ 达到饱和的最优方式是将边定向为 $2 \to 3$、$1 \to 2$；此时仅顶点 $3$ 是饱和的，因此答案为 $5$。

第二个例子中的最优策略是沿环定向各条边：$1 \to 2$、$2 \to 3$、$3 \to 4$ 和 $4 \to 1$。这样，所有顶点均达到饱和。