CF1081D.Maximum Distance

Chouti was tired of the tedious homework, so he opened up an old programming problem he created years ago.

You are given a connected undirected graph with $n$ vertices and $m$ weighted edges. There are $k$ special vertices: $x_1, x_2, \ldots, x_k$.

Let's define the cost of the path as the maximum weight of the edges in it. And the distance between two vertexes as the minimum cost of the paths connecting them.

For each special vertex, find another special vertex which is farthest from it (in terms of the previous paragraph, i.e. the corresponding distance is maximum possible) and output the distance between them.

The original constraints are really small so he thought the problem was boring. Now, he raises the constraints and hopes you can solve it for him.

Chouti 厌倦了枯燥的作业，于是打开了一道多年前自己创建的旧编程题。

你被给定一个包含 $n$ 个顶点和 $m$ 条带权无向边的连通无向图。其中有 $k$ 个特殊顶点：$x_1, x_2, \ldots, x_k$。

我们定义一条路径的代价为该路径中所有边的最大权重；并定义两个顶点之间的距离为连接它们的所有路径中代价的最小值。

对每个特殊顶点，找出另一个与它距离最远的特殊顶点（即按上述定义，对应的距离取最大可能值），并输出该距离。

原题约束非常小，因此他觉得这道题很无聊。现在，他提高了约束条件，希望你能帮他解决这个问题。

The first line contains three integers $n$, $m$ and $k$ ($2 \leq k \leq n \leq 10^5$, $n-1 \leq m \leq 10^5$) — the number of vertices, the number of edges and the number of special vertices.

The second line contains $k$ distinct integers $x_1, x_2, \ldots, x_k$ ($1 \leq x_i \leq n$).

Each of the following $m$ lines contains three integers $u$, $v$ and $w$ ($1 \leq u,v \leq n, 1 \leq w \leq 10^9$), denoting there is an edge between $u$ and $v$ of weight $w$. The given graph is undirected, so an edge $(u, v)$ can be used in the both directions.

The graph may have multiple edges and self-loops.

It is guaranteed, that the graph is connected.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq k \leq n \leq 10^5$，$n-1 \leq m \leq 10^5$），分别表示顶点数、边数和特殊顶点数。

第二行包含 $k$ 个互不相同的整数 $x_1, x_2, \ldots, x_k$（$1 \leq x_i \leq n$）。

接下来的 $m$ 行每行包含三个整数 $u$、$v$ 和 $w$（$1 \leq u,v \leq n$，$1 \leq w \leq 10^9$），表示在顶点 $u$ 与 $v$ 之间存在一条权重为 $w$ 的边。给定图是无向图，因此边 $(u, v)$ 可沿两个方向使用。

该图可能包含重边和自环。

保证图是连通的。

The first and only line should contain $k$ integers. The $i$-th integer is the distance between $x_i$ and the farthest special vertex from it.

第一行且仅有一行，应包含 $k$ 个整数。其中第 $i$ 个整数表示 $x_i$ 到距离它最远的特殊顶点的距离。

In the first example, the distance between vertex $1$ and $2$ equals to $2$ because one can walk through the edge of weight $2$ connecting them. So the distance to the farthest node for both $1$ and $2$ equals to $2$.

In the second example, one can find that distance between $1$ and $2$, distance between $1$ and $3$ are both $3$ and the distance between $2$ and $3$ is $2$.

The graph may have multiple edges between and self-loops, as in the first example.

在第一个例子中，顶点 $1$ 与 $2$ 之间的距离为 $2$，因为可以通过连接它们的、权值为 $2$ 的边行走。因此，顶点 $1$ 和 $2$ 到各自最远节点的距离均为 $2$。

在第二个例子中，可以发现：顶点 $1$ 与 $2$ 之间的距离、顶点 $1$ 与 $3$ 之间的距离均为 $3$，而顶点 $2$ 与 $3$ 之间的距离为 $2$。

该图可能包含顶点之间的多条边以及自环，如第一个例子所示。