CF1343E.Weights Distributing

You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges (which represents the map of Bertown) and the array of prices $p$ of length $m$. It is guaranteed that there is a path between each pair of vertices (districts).

Mike has planned a trip from the vertex (district) $a$ to the vertex (district) $b$ and then from the vertex (district) $b$ to the vertex (district) $c$. He can visit the same district twice or more. But there is one issue: authorities of the city want to set a price for using the road so if someone goes along the road then he should pay the price corresponding to this road (he pays each time he goes along the road). The list of prices that will be used $p$ is ready and they just want to distribute it between all roads in the town in such a way that each price from the array corresponds to exactly one road.

You are a good friend of Mike (and suddenly a mayor of Bertown) and want to help him to make his trip as cheap as possible. So, your task is to distribute prices between roads in such a way that if Mike chooses the optimal path then the price of the trip is the minimum possible. Note that you cannot rearrange prices after the start of the trip.

You have to answer $t$ independent test cases.

你被给定一个包含 $n$ 个顶点和 $m$ 条边的无向无权图（代表 Bertown 的地图），以及一个长度为 $m$ 的价格数组 $p$。保证任意两个顶点（城区）之间均存在路径。

Mike 计划一次旅行：从顶点（城区）$a$ 出发，到达顶点（城区）$b$，再从 $b$ 出发到达顶点（城区）$c$。他可以多次访问同一城区。但存在一个问题：该市当局希望为每条道路设定通行费用；即，若某人经过某条道路，则需支付对应于此道路的费用（每次经过均需支付）。用于收费的价格列表 $p$ 已确定，他们仅需将这些价格分配给城镇中的所有道路，使得数组 $p$ 中的每个价格恰好对应一条道路。

你是 Mike 的好朋友（同时意外地担任 Bertown 市长），希望帮助他使此次旅行的总费用尽可能低。因此，你的任务是将价格分配给各条道路，使得当 Mike 选择最优路径时，整个行程的总费用达到最小可能值。注意：在旅行开始后，你不能再重新调整价格的分配。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains five integers $n, m, a, b$ and $c$ ($2 \le n \le 2 \cdot 10^5$, $n-1 \le m \le min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$, $1 \le a, b, c \le n$) — the number of vertices, the number of edges and districts in Mike's trip.

The second line of the test case contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \le 10^9$), where $p_i$ is the $i$-th price from the array.

The following $m$ lines of the test case denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the array of edges, and for each pair $(v_i, u_i)$ the condition $v_i \ne u_i$ is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that the sum of $n$ (as well as the sum of $m$) does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$, $\sum m \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含五个整数 $n, m, a, b$ 和 $c$（$2 \le n \le 2 \cdot 10^5$，$n-1 \le m \le \min\left(\frac{n(n-1)}{2},\, 2 \cdot 10^5\right)$，$1 \le a, b, c \le n$），分别表示图中顶点的数量、边的数量，以及 Mike 旅行所涉及的三个区域编号。

每个测试用例的第二行包含 $m$ 个整数 $p_1, p_2, \dots, p_m$（$1 \le p_i \le 10^9$），其中 $p_i$ 表示价格数组中的第 $i$ 个价格。

接下来的 $m$ 行描述图中的边：第 $i$ 条边由一对整数 $v_i, u_i$（$1 \le v_i, u_i \le n$，$u_i \ne v_i$）表示，即该边连接的两个顶点的编号。给定图中不存在自环或重边，即对于任意一对 $(v_i, u_i)$，数组中不会出现另一对完全相同的 $(v_i, u_i)$ 或反向的 $(u_i, v_i)$；且对每条边 $(v_i, u_i)$ 均满足 $v_i \ne u_i$。保证给定图是连通的。

保证所有测试用例的 $n$ 之和（以及 $m$ 之和）均不超过 $2 \cdot 10^5$（即 $\sum n \le 2 \cdot 10^5$，$\sum m \le 2 \cdot 10^5$）。

For each test case, print the answer — the minimum possible price of Mike's trip if you distribute prices between edges optimally.

对于每个测试用例，输出答案——即在最优地将价格分配给各条边的情况下，Mike 旅行的最小可能价格。

One of the possible solution to the first test case of the example:

One of the possible solution to the second test case of the example:

示例中第一个测试用例的一种可能解法：

示例中第二个测试用例的一种可能解法：