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.


-----Input-----

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


-----Output-----

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


-----Example-----
Input
2
4 3 2 3 4
1 2 3
1 2
1 3
1 4
7 9 1 5 7
2 10 4 8 5 6 7 3 3
1 2
1 3
1 4
3 2
3 5
4 2
5 6
1 7
6 7

Output
7
12



-----Note-----

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

[Image]

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

[Image]

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Sorting

Greedy algorithms

Complete search


Solutions:
from collections import deque
g = [[] for y in range(int(200000.0 + 5))]
q = int(input())
while q > 0:
	q -= 1
	(n, m, a, b, c) = map(int, input().split())

	def BFS(a):
		List = []
		dist = [-1] * (n + 1)
		dist[a] = 0
		List = deque([a])
		while List:
			u = List.popleft()
			for v in g[u]:
				if dist[v] < 0:
					dist[v] = dist[u] + 1
					List.append(v)
		return dist
	p = list(map(int, input().split()))
	p.sort()
	p.insert(0, 0)
	for i in range(1, n + 1):
		g[i].clear()
	for i in range(1, m + 1):
		p[i] = p[i] + p[i - 1]
	for i in range(1, m + 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	dist1 = []
	dist2 = []
	dist3 = []
	dist1.extend(BFS(a))
	dist2.extend(BFS(b))
	dist3.extend(BFS(c))
	res = int(1e+17)
	for i in range(1, n + 1):
		if dist1[i] + dist2[i] + dist3[i] > m:
			continue
		res = min(res, p[dist2[i]] + p[dist1[i] + dist2[i] + dist3[i]])
	print(res)


import math
from collections import defaultdict
T = int(input())

def dfs(edges, node):
	nodes = {node}
	res = {node: 0}
	visited = {node}
	d = 0
	while nodes:
		d += 1
		next_nodes = set()
		for node in nodes:
			for edge in edges[node]:
				if edge in visited:
					continue
				visited.add(edge)
				next_nodes.add(edge)
				res[edge] = d
		nodes = next_nodes
	return res
for t in range(T):
	(N, M, A, B, C) = [int(i) for i in input().split()]
	P = sorted([int(i) for i in input().split()])
	pp = [0]
	for p in P:
		pp.append(pp[-1] + p)
	edges = defaultdict(list)
	for m in range(M):
		(u, v) = [int(i) for i in input().split()]
		edges[u].append(v)
		edges[v].append(u)
	dfsA = dfs(edges, A)
	dfsB = dfs(edges, B)
	dfsC = dfs(edges, C)
	answer = math.inf
	for m in range(1, N + 1):
		if dfsA[m] + dfsB[m] + dfsC[m] < len(pp):
			answer = min(answer, pp[dfsA[m] + dfsB[m] + dfsC[m]] + pp[dfsB[m]])
	print(answer)


from collections import defaultdict, deque

def bfs(s, d):
	d[s] = 0
	que = deque([s])
	while que:
		v = que.popleft()
		for nv in edges[v]:
			if d[nv] == inf:
				que.append(nv)
				d[nv] = d[v] + 1

def solver():
	price.sort()
	pf = [0] * (m + 1)
	for i in range(1, m + 1):
		pf[i] = pf[i - 1] + price[i]
	(da, db, dc) = ([inf] * (n + 1), [inf] * (n + 1), [inf] * (n + 1))
	bfs(a, da)
	bfs(b, db)
	bfs(c, dc)
	ans = inf
	for i in range(1, n + 1):
		if da[i] + db[i] + dc[i] > m:
			continue
		dx = db[i]
		posans = pf[dx] + pf[da[i] + dc[i] + dx]
		ans = min(ans, posans)
	return ans
inf = float('inf')
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	price = [0]
	price.extend(map(int, input().split()))
	edges = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		edges[u].append(v)
		edges[v].append(u)
	ans = solver()
	print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7

def dijkstra(n, graph, start):
	dist = [float('inf')] * n
	dist[start] = 0
	edge_len = 1
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for w in graph[v]:
				if edge_len + path_len < dist[w]:
					dist[w] = edge_len + path_len
					heappush(queue, (edge_len + path_len, w))
	return dist
for t in range(int(data())):
	(n, m, a, b, c) = mdata()
	a -= 1
	b -= 1
	c -= 1
	g = [[] for i in range(n)]
	P = [0]
	P += sorted(mdata())
	for i in range(1, m + 1):
		P[i] = P[i - 1] + P[i]
	for i in range(m):
		(u, v) = mdata()
		(u, v) = (u - 1, v - 1)
		g[u].append(v)
		g[v].append(u)
	dist_a = dijkstra(n, g, a)
	dist_b = dijkstra(n, g, b)
	dist_c = dijkstra(n, g, c)
	ans = INF
	for i in range(n):
		if dist_b[i] + dist_a[i] + dist_c[i] > m:
			continue
		ans = min(ans, P[dist_b[i]] + P[dist_b[i] + dist_a[i] + dist_c[i]])
	out(ans)


from collections import deque

def readGraph(n, m):
	adj = [set() for i in range(n + 1)]
	for i in range(m):
		(v1, v2) = [int(x) for x in input().split()]
		adj[v1].add(v2)
		adj[v2].add(v1)
	return adj

def bfs(adj, src, n):
	q = deque()
	q.append(src)
	visited = [False] * (n + 1)
	distance = [0] * (n + 1)
	visited[src] = True
	while q:
		ele = q.popleft()
		for a in adj[ele]:
			if visited[a] == False:
				q.append(a)
				distance[a] = distance[ele] + 1
				visited[a] = True
	return distance

def solve():
	(n, m, a, b, c) = [int(x) for x in input().split()]
	p = [0] + [int(x) for x in input().split()]
	adj = readGraph(n, m)
	dA = bfs(adj, a, n)
	dB = bfs(adj, b, n)
	dC = bfs(adj, c, n)
	p.sort()
	psum = [0] * (m + 1)
	psum[1] = p[0]
	for i in range(1, m + 1):
		psum[i] = psum[i - 1] + p[i]
	pay = 99999999999999999999999999999999
	for D in range(1, n + 1):
		DA = dA[D]
		DB = dB[D]
		DC = dC[D]
		if DA + DB + DC <= m:
			pay = min(pay, psum[DB] + psum[DA + DB + DC])
	print(pay)
t = int(input())
for i in range(t):
	solve()


import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
	q = deque([s])
	dist = [-1] * n
	dist[s] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	G = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
	d1 = bfs(a - 1)
	d2 = bfs(b - 1)
	d3 = bfs(c - 1)
	p.sort()
	acc = [0] * (m + 1)
	for i in range(m):
		acc[i + 1] = acc[i] + p[i]
	ans = 10 ** 18
	for i in range(n):
		c1 = d1[i]
		c2 = d2[i]
		c3 = d3[i]
		if c1 + c2 + c3 > m:
			continue
		ans = min(ans, 2 * acc[c2] + acc[c1 + c2 + c3] - acc[c2])
	print(ans)


from itertools import accumulate
from collections import deque

def BFS(adj, level, s):
	queue = deque([s])
	level[s] = 0
	while queue:
		s = queue.popleft()
		for i in adj[s]:
			if level[i] == -1:
				queue.append(i)
				level[i] = level[s] + 1

def addEdge(adj, v, w):
	adj[v].append(w)
	adj[w].append(v)
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split(' '))
	(a, b, c) = (a - 1, b - 1, c - 1)
	p = [int(x) for x in input().split()]
	p.sort()
	cost = [0] + list(accumulate(p))
	adj = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split(' '))
		addEdge(adj, u - 1, v - 1)
	(da, db, dc) = ([-1] * n, [-1] * n, [-1] * n)
	BFS(adj, da, a)
	BFS(adj, db, b)
	BFS(adj, dc, c)
	ans = 10 ** 18
	for i in range(n):
		x = da[i] + db[i] + dc[i]
		if x <= m:
			cx = cost[x] + cost[db[i]]
			ans = min(ans, cx)
	print(ans)


from collections import deque
from itertools import accumulate
from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m, a, b, c) = [int(x) for x in stdin.readline().split()]
	p = list(accumulate([0, *sorted((int(x) for x in stdin.readline().split()))]))
	adj = [[] for i in range(n + 1)]
	for e in range(m):
		(u, v) = [int(x) for x in stdin.readline().split()]
		adj[u].append(v)
		adj[v].append(u)
	(da, db, dc) = ([-1 for i in range(n + 1)], [-1 for i in range(n + 1)], [-1 for i in range(n + 1)])
	for (s, d) in ((a, da), (b, db), (c, dc)):
		q = deque([s])
		d[s] = 0
		while len(q) > 0:
			u = q.popleft()
			for v in adj[u]:
				if d[v] == -1:
					d[v] = d[u] + 1
					q.append(v)
	print(min((p[db[x]] + p[db[x] + da[x] + dc[x]] for x in range(1, n + 1) if db[x] + da[x] + dc[x] < n)))


from sys import stdin
input = stdin.readline

def bfs(g, r):
	it = -1
	p = [0] * len(g)
	q = [r]
	v = [0] * len(g)
	while it < len(q) - 1:
		it += 1
		v[q[it]] = 1
		for i in range(len(g[q[it]])):
			if v[g[q[it]][i]] == 0:
				v[g[q[it]][i]] = 1
				q.append(g[q[it]][i])
				p[g[q[it]][i]] = p[q[it]] + 1
	return p
for _ in range(int(input())):
	(n, k, a, b, c) = map(int, input().split())
	ax = list(map(int, input().split()))
	g = [[] for i in range(n)]
	a -= 1
	b -= 1
	c -= 1
	d = {}
	for i in range(k):
		(l, r) = map(int, input().split())
		g[l - 1].append(r - 1)
		g[r - 1].append(l - 1)
		d[min(l - 1, r - 1), max(l - 1, r - 1)] = 0
	aa = bfs(g, a)
	bb = bfs(g, b)
	cc = bfs(g, c)
	ax.sort()
	x = [0]
	y = 0
	for i in range(k):
		y += ax[i]
		x.append(y)
	ans = 10 ** 19
	for i in range(n):
		if aa[i] + bb[i] + cc[i] > k:
			continue
		ans = min(ans, x[bb[i]] + x[aa[i] + bb[i] + cc[i]])
	print(ans)


from collections import deque
import sys
input = sys.stdin.readline
inf = int(1000000000.0)
for i in range(int(input())):
	(n, m, a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c -= 1
	cost = list(map(int, input().split()))
	g = [[] for _ in range(n)]
	for i in range(m):
		(a2, b2) = map(int, input().split())
		g[a2 - 1].append(b2 - 1)
		g[b2 - 1].append(a2 - 1)

	def bfs(st):
		Q = deque(maxlen=n)
		lv = [-1] * n
		Q.append(st)
		lv[st] = 0
		while Q:
			cur = Q.popleft()
			for to in g[cur]:
				if lv[to] == -1:
					lv[to] = lv[cur] + 1
					Q.append(to)
		return lv
	lvA = bfs(a)
	lvB = bfs(b)
	lvC = bfs(c)
	ans = int(1e+18)
	cost.sort()
	cost.insert(0, 0)
	for i in range(1, len(cost)):
		cost[i] += cost[i - 1]
	for i in range(n):
		d1 = lvB[i]
		d2 = lvA[i] + lvC[i]
		if d1 + d2 >= len(cost):
			continue
		ans = min(ans, cost[d1] * 2 + cost[d1 + d2] - cost[d1])
	print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def outln(var):
	sys.stdout.write(str(var) + '\n')

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def bfs(source):
	d = deque()
	d.append(source)
	dist = dd(lambda : mod)
	dist[source] = 0
	while d:
		temp = d.popleft()
		for child in graph[temp]:
			if dist[child] > dist[temp] + 1:
				d.append(child)
				dist[child] = dist[temp] + 1
	return dist
for _ in range(int(data())):
	(n, m, a, b, z) = sp()
	arr = l()
	arr.sort()
	for i in range(1, m):
		arr[i] += arr[i - 1]
	arr.insert(0, 0)
	graph = dd(set)
	for i in range(m):
		(u, v) = sp()
		graph[u].add(v)
		graph[v].add(u)
	(dista, distb, distc) = (bfs(a), bfs(b), bfs(z))
	answer = pow(10, 19)
	for i in range(1, n + 1):
		if dista[i] + distb[i] + distc[i] <= m:
			answer = min(answer, arr[distb[i]] + arr[dista[i] + distb[i] + distc[i]])
	outln(answer)


import collections
tests = int(input())

def bfs(start, edges):
	q = collections.deque([start])
	dist = [-1] * (n + 1)
	dist[start] = 0
	while len(q) > 0:
		curr_node = q.popleft()
		for (idx, neighbour) in enumerate(edges[curr_node]):
			if dist[neighbour] == -1:
				q.append(neighbour)
				dist[neighbour] = dist[curr_node] + 1
	return dist
for t in range(tests):
	(n, m, a, b, c) = map(int, input().split(' '))
	costs = map(int, input().split(' '))
	costs = sorted(costs)
	dist = [[-1, -1, -1] for i in range(n + 1)]
	edges = [[] for i in range(n + 1)]
	partial_sums = [0]
	for (nod, cost) in enumerate(costs):
		costs[nod] = cost
		partial_sums.append(partial_sums[nod] + cost)
	for edge in range(m):
		(u, v) = map(int, input().split(' '))
		edges[u].append(v)
		edges[v].append(u)
	dist = [[], [], []]
	dist[0] = bfs(a, edges)
	dist[1] = bfs(b, edges)
	dist[2] = bfs(c, edges)
	min_sum = 1 << 62
	for i in range(1, n + 1, 1):
		if dist[0][i] + dist[1][i] + dist[2][i] > m:
			continue
		min_sum = min(min_sum, partial_sums[dist[1][i]] + partial_sums[dist[0][i] + dist[1][i] + dist[2][i]])
	print(min_sum)


from collections import deque
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	g = [[] for i in range(n + 5)]
	cost = list(map(int, input().split(' ')))
	cost.insert(0, 0)
	cost.sort()
	for i in range(m):
		cost[i + 1] += cost[i]
	for _ in range(m):
		(u, v) = map(int, input().split(' '))
		g[u].append(v)
		g[v].append(u)

	def BFS(source):
		dis = [-1] * (n + 1)
		dis[source] = 0
		q = deque([source])
		while q:
			cur = q.popleft()
			for i in g[cur]:
				if dis[i] == -1:
					dis[i] = 1 + dis[cur]
					q.append(i)
		return dis
	dis1 = []
	dis2 = []
	dis3 = []
	dis1.extend(BFS(a))
	dis2.extend(BFS(b))
	dis3.extend(BFS(c))
	ans = 2e+18
	for i in range(1, n + 1):
		temp = dis1[i] + dis2[i] + dis3[i]
		if temp > m:
			continue
		ans = min(ans, cost[dis2[i]] + cost[temp])
	print(ans)


import collections
tests = int(input())

def bfs(start, edges):
	q = collections.deque([start])
	D = [-1] * (n + 1)
	D[start] = 0
	while len(q) > 0:
		curr_node = q.popleft()
		for (idx, neighbour) in enumerate(edges[curr_node]):
			if D[neighbour] < 0:
				q.append(neighbour)
				D[neighbour] = D[curr_node] + 1
	return D
for t in range(tests):
	(n, m, a, b, c) = map(int, input().split(' '))
	costs = list(map(int, input().split(' ')))
	costs.sort()
	edges = [[] for i in range(n + 1)]
	partial_sums = [0]
	for (idx, cost) in enumerate(costs):
		costs[idx] = cost
		partial_sums.append(partial_sums[idx] + cost)
	for edge in range(m):
		(u, v) = map(int, input().split(' '))
		edges[u].append(v)
		edges[v].append(u)
	D = [[] for i in range(3)]
	D[0] = bfs(a, edges)
	D[1] = bfs(b, edges)
	D[2] = bfs(c, edges)
	min_sum = 1 << 63
	for i in range(1, n + 1, 1):
		D_path = D[0][i] + D[1][i] + D[2][i]
		if D_path > m:
			continue
		min_sum = min(min_sum, partial_sums[D[1][i]] + partial_sums[D[0][i] + D[1][i] + D[2][i]])
	print(min_sum)


from collections import deque

def bfs(start, e, n):
	dist = [-1] * n
	queue = deque([start])
	dist[start] = 0
	while queue:
		here = queue.popleft()
		for next in e[here]:
			if dist[next] == -1:
				queue.append(next)
				dist[next] = dist[here] + 1
	return dist
t = int(input())
for T in range(t):
	(n, m, a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c -= 1
	p = list(map(int, input().split()))
	p.sort()
	e = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		e[u].append(v)
		e[v].append(u)
	u = bfs(a, e, n)
	v = bfs(b, e, n)
	w = bfs(c, e, n)
	psum = [0] + p
	for i in range(m):
		psum[i + 1] += psum[i]
	ans = 10000000000000000
	for x in range(n):
		one = u[x]
		two = v[x]
		thr = w[x]
		if one + two + thr > m:
			continue
		ans = min(ans, psum[two] + psum[one + two + thr])
	print(ans)


from itertools import accumulate
from collections import deque
import sys
input = sys.stdin.readline
inf = 100000000000000000

def bfs(STA):
	DIS = [-1] * (n + 1)
	Q = deque([STA])
	DIS[STA] = 0
	while Q:
		x = Q.pop()
		for to in A[x]:
			if DIS[to] == -1:
				DIS[to] = DIS[x] + 1
				Q.appendleft(to)
	return DIS
for test in range(int(input())):
	(n, m, s, ss, sss) = map(int, input().split())
	B = sorted(map(int, input().split()))
	S = [0] + list(accumulate(B))
	A = [[] for i in range(n + 3)]
	for i in range(m):
		(x, y) = map(int, input().split())
		A[x].append(y)
		A[y].append(x)
	DIS_A = bfs(s)
	DIS_B = bfs(ss)
	DIS_C = bfs(sss)
	ans = inf
	if DIS_A[ss] + DIS_B[sss] <= m:
		ans = S[DIS_A[ss] + DIS_B[sss]]
	for i in range(1, n + 1):
		dis2 = inf
		dis1 = S[DIS_B[i]]
		if DIS_B[i] + DIS_A[i] + DIS_C[i] <= m:
			dis2 = S[DIS_B[i] + DIS_A[i] + DIS_C[i]]
			ans = min(ans, dis1 + dis2)
	print(ans)


from collections import deque
import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def bfs(n, adj, start):
	cost = [-1] * n
	cost[start] = 0
	dq = deque([start])
	while dq:
		v = dq.popleft()
		for dest in adj[v]:
			if cost[dest] != -1:
				continue
			cost[dest] = cost[v] + 1
			dq.append(dest)
	return cost

def main():
	t = int(input())
	ans = [''] * t
	for ti in range(t):
		from itertools import accumulate
		(n, m, a, b, c) = map(int, input().split())
		(a, b, c) = (a - 1, b - 1, c - 1)
		p = (0,) + tuple(accumulate(sorted(map(int, input().split()))))
		adj = [[] for _ in range(n)]
		for (u, v) in (map(int, input().split()) for _ in range(m)):
			adj[u - 1].append(v - 1)
			adj[v - 1].append(u - 1)
		a_to_x = bfs(n, adj, a)
		b_to_x = bfs(n, adj, b)
		c_to_x = bfs(n, adj, c)
		mincost = 10 ** 18
		for x in range(n):
			if a_to_x[x] + b_to_x[x] + c_to_x[x] > m:
				continue
			mincost = min(mincost, p[b_to_x[x]] + p[a_to_x[x] + b_to_x[x] + c_to_x[x]])
		ans[ti] = str(mincost)
	sys.stdout.buffer.write(('\n'.join(ans) + '\n').encode('utf-8'))
main()


import collections
infty = 10 ** 15

def bfs(n, g, x):
	dx = [infty] * (n + 1)
	dx[x] = 0
	visited = set([x])
	queue = collections.deque([(x, 0)])
	while queue:
		(s, dist) = queue.popleft()
		for v in g[s]:
			if v not in visited:
				visited.add(v)
				dx[v] = dist + 1
				queue.append((v, dx[v]))
	return dx
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	g = [[] for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		g[x].append(y)
		g[y].append(x)
	da = bfs(n, g, a)
	db = bfs(n, g, b)
	dc = bfs(n, g, c)
	p.sort()
	psum = [0, p[0]]
	for j in range(1, m):
		psum.append(psum[-1] + p[j])
	ans = infty
	for q in range(1, n + 1):
		if da[q] + db[q] + dc[q] <= m:
			ans = min(ans, psum[da[q] + db[q] + dc[q]] + psum[db[q]])
	print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		(N, M, a, b, c) = map(int, input().split())
		P = list(map(int, input().split()))
		P.sort()
		cs = [0] * (M + 1)
		for i in range(M):
			cs[i + 1] = cs[i] + P[i]
		adj = [[] for _ in range(N + 1)]
		for _ in range(M):
			(u, v) = map(int, input().split())
			adj[u].append(v)
			adj[v].append(u)
		v0_list = [a, b, c]
		seen_list = [[-1] * (N + 1) for _ in range(3)]
		for (i, v0) in enumerate(v0_list):
			seen = seen_list[i]
			que = deque()
			que.append(v0)
			seen[v0] = 0
			while que:
				v = que.popleft()
				for u in adj[v]:
					if seen[u] == -1:
						seen[u] = seen[v] + 1
						que.append(u)
		ans = float('inf')
		for d in range(1, N + 1):
			na = seen_list[0][d]
			nb = seen_list[1][d]
			nc = seen_list[2][d]
			if na + nb + nc > M:
				continue
			ans = min(ans, cs[nb] + cs[na + nb + nc])
		print(ans)
main()


import sys
from collections import deque
from itertools import accumulate

def bfs(n, s, links):
	q = deque([(0, s)])
	visited = set()
	distances = [0] * n
	while q:
		(d, v) = q.popleft()
		if v in visited:
			continue
		visited.add(v)
		distances[v] = d
		q.extend(((d + 1, u) for u in links[v] if u not in visited))
	return distances
ipt = list(map(int, sys.stdin.buffer.read().split()))
buf = []
t = ipt[0]
k = 1
INF = 10 ** 18
for _ in range(t):
	(n, m, a, b, c) = ipt[k:k + 5]
	ppp = ipt[k + 5:k + 5 + m]
	uv = ipt[k + 5 + m:k + 5 + 3 * m]
	k += 5 + 3 * m
	ppp.sort()
	ppp_acc = [0] + list(accumulate(ppp))
	links = [set() for _ in range(n)]
	for (u, v) in zip(uv[0::2], uv[1::2]):
		u -= 1
		v -= 1
		links[u].add(v)
		links[v].add(u)
	from_a = bfs(n, a - 1, links)
	from_b = bfs(n, b - 1, links)
	from_c = bfs(n, c - 1, links)
	ans = INF
	for (fa, fb, fc) in zip(from_a, from_b, from_c):
		fs = fa + fb + fc
		if fs > m:
			continue
		ans = min(ans, ppp_acc[fb] + ppp_acc[fs])
	buf.append(ans)
print('\n'.join(map(str, buf)))


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
	from collections import deque
	N = len(nodes)
	que = deque([(src, 0)])
	dist = [INF] * N
	dist[src] = 0
	while que:
		(u, c) = que.popleft()
		for v in nodes[u]:
			if dist[v] != INF:
				continue
			dist[v] = c + 1
			que.append((v, c + 1))
	return dist
out = []
for _ in range(INT()):
	(N, M, x, y, z) = MAP()
	x -= 1
	y -= 1
	z -= 1
	cost = LIST()
	nodes = [[] for i in range(N)]
	for _ in range(M):
		(a, b) = MAP()
		a -= 1
		b -= 1
		nodes[a].append(b)
		nodes[b].append(a)
	cntx = bfs(nodes, x)
	cnty = bfs(nodes, y)
	cntz = bfs(nodes, z)
	cost.sort()
	cost = [0] + list(accumulate(cost))
	ans = INF
	for i in range(N):
		total = cntx[i] + cnty[i] + cntz[i]
		if total > M:
			continue
		ans = min(ans, cost[total] + cost[cnty[i]])
	out.append(str(ans))
print('\n'.join(out))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def bfs(s):
	dist = [-1] * n
	dist[s] = 0
	q = deque()
	q.append(s)
	while q:
		now = q.popleft()
		for nx in g[now]:
			if dist[nx] == -1:
				dist[nx] = dist[now] + 1
				q.append(nx)
	return dist
for i in range(inp()):
	(n, m, a, b, c) = inpl()
	a -= 1
	b -= 1
	c -= 1
	p = inpl()
	g = [[] for _ in range(n)]
	for _ in range(m):
		(x, y) = inpl_1()
		g[x].append(y)
		g[y].append(x)
	p.sort()
	pp = p[:]
	p = [0]
	for x in pp:
		p.append(p[-1] + x)
	A = bfs(a)
	B = bfs(b)
	C = bfs(c)
	res = INF
	for i in range(n):
		if A[i] + B[i] + C[i] <= m:
			ans = p[A[i] + B[i] + C[i]] + p[B[i]]
			res = min(res, ans)
	print(res)


from collections import deque
from itertools import accumulate
from sys import stdin
t = int(input())
for i in range(0, t):
	(n, m, a, b, c) = [int(x) for x in stdin.readline().split()]
	p = list(accumulate([0, *sorted((int(x) for x in stdin.readline().split()))]))
	graph = [[] for i in range(0, n + 1)]
	for j in range(m):
		(x, y) = [int(x) for x in stdin.readline().split()]
		graph[x].append(y)
		graph[y].append(x)
	(da, db, dc) = ([-1 for i in range(n + 1)], [-1 for i in range(n + 1)], [-1 for i in range(n + 1)])
	for (s, d) in ((a, da), (b, db), (c, dc)):
		q = deque([s])
		d[s] = 0
		while len(q) > 0:
			cur = q.popleft()
			for next in graph[cur]:
				if d[next] == -1:
					d[next] = d[cur] + 1
					q.append(next)
	print(min((p[db[x]] + p[db[x] + da[x] + dc[x]] for x in range(1, n + 1) if db[x] + da[x] + dc[x] < n)))


from collections import deque
from sys import stdin, stdout
int1 = lambda x: int(x) - 1

def MI():
	return map(int, stdin.readline().split())

def MI1():
	return map(int1, stdin.readline().split())

def LI():
	return list(map(int, stdin.readline().split()))

def BFS(adj, level, s):
	queue = deque([s])
	level[s] = 0
	while queue:
		s = queue.popleft()
		for i in adj[s]:
			if level[i] == -1:
				queue.append(i)
				level[i] = level[s] + 1
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = MI()
	(a, b, c) = (a - 1, b - 1, c - 1)
	p = LI()
	cost = [0]
	p.sort()
	for x in p:
		cost.append(cost[-1] + x)
	adj = [[] for i in range(n)]
	for i in range(m):
		(u, v) = MI1()
		adj[u].append(v)
		adj[v].append(u)
	(da, db, dc) = ([-1] * n, [-1] * n, [-1] * n)
	BFS(adj, da, a)
	BFS(adj, db, b)
	BFS(adj, dc, c)
	ans = 10 ** 18
	for i in range(n):
		x = da[i] + db[i] + dc[i]
		if x <= m:
			cx = cost[x] + cost[db[i]]
			ans = min(ans, cx)
	stdout.write(str(ans) + '\n')


import sys
input = sys.stdin.readline
from itertools import accumulate
from collections import deque

def bfs(x):
	DIS = [-1] * (n + 1)
	Q = deque([x])
	DIS[x] = 0
	while Q:
		x = Q.pop()
		for to in E[x]:
			if DIS[to] == -1:
				DIS[to] = DIS[x] + 1
				Q.appendleft(to)
	return DIS
t = int(input())
for tests in range(t):
	(n, m, a, b, c) = map(int, input().split())
	P = sorted(map(int, input().split()))
	S = [0] + list(accumulate(P))
	E = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		E[x].append(y)
		E[y].append(x)
	DIS_A = bfs(a)
	DIS_B = bfs(b)
	DIS_C = bfs(c)
	ANS = 1 << 63
	if DIS_A[b] + DIS_B[c] <= m and ANS > S[DIS_A[b] + DIS_B[c]]:
		ANS = S[DIS_A[b] + DIS_B[c]]
	for i in range(1, n + 1):
		d2 = DIS_B[i]
		d1 = DIS_A[i] + DIS_C[i]
		if d1 + d2 > m:
			continue
		if ANS > S[d2] * 2 + S[d1 + d2] - S[d2]:
			ANS = S[d2] * 2 + S[d1 + d2] - S[d2]
	print(ANS)


import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, UserDict, defaultdict, deque, namedtuple
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush
input = sys.stdin.readline
write = sys.stdout.write
MOD = 10 ** 9 + 7
INT_MAX = (1 << 63) - 1

def calc_distance(frm, graph, n):
	pq = [(0, frm)]
	dist = [INT_MAX] * (n + 1)
	dist[frm] = 0
	while pq:
		(d, node) = heappop(pq)
		if d > dist[node]:
			continue
		for nb in graph[node]:
			if 1 + d < dist[nb]:
				dist[nb] = 1 + d
				heappush(pq, (1 + d, nb))
	return dist
T = int(input())
for _ in range(T):
	(n, m, a, b, c) = map(int, input().split())
	prices = list(map(int, input().split()))
	prices.sort()
	edge = {}
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	to_a = calc_distance(a, graph, n)
	to_b = calc_distance(b, graph, n)
	to_c = calc_distance(c, graph, n)
	prefix = [0] * (m + 1)
	for (i, p) in enumerate(prices):
		prefix[i + 1] = p + prefix[i]
	ans = INT_MAX
	for v in range(1, n + 1):
		(d_a, d_b, d_c) = (to_a[v], to_b[v], to_c[v])
		if d_a + d_b + d_c <= m:
			cur = prefix[d_a + d_b + d_c] + prefix[d_b]
			if cur < ans:
				ans = cur
	write(str(ans) + '\n')


from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
	q = deque([start])
	dist = [-1] * n
	dist[start] = 0
	while q:
		v = q.popleft()
		for nxt_v in graph[v]:
			if dist[nxt_v] != -1:
				continue
			dist[nxt_v] = dist[v] + 1
			q.append(nxt_v)
	return dist
t = int(input())
INF = 10 ** 18
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	info = [list(map(int, input().split())) for i in range(m)]
	(a, b, c) = (a - 1, b - 1, c - 1)
	p = sorted(p)
	ru = [0] * (m + 1)
	for i in range(m):
		ru[i + 1] = ru[i] + p[i]
	graph = [[] for i in range(n)]
	for (u, v) in info:
		(u, v) = (u - 1, v - 1)
		graph[u].append(v)
		graph[v].append(u)
	dist_a = bfs(a)
	dist_b = bfs(b)
	dist_c = bfs(c)
	ans = 10 ** 18
	for i in range(n):
		(l, mid, r) = (0, dist_b[i], dist_a[i] + dist_b[i] + dist_c[i])
		if r >= len(ru):
			continue
		ans = min(ans, 2 * (ru[mid] - ru[l]) + (ru[r] - ru[mid]))
	print(ans)


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for i in range(t):
	(n, m, a, b, c) = (int(x) for x in input().split())
	p = list(map(int, input().split()))
	p.sort()
	connected = [[] for _ in range(n + 1)]
	for j in range(1, m + 1):
		(v, u) = (int(x) for x in input().split())
		connected[v].append(u)
		connected[u].append(v)
	cs = [0]
	for j in range(m):
		cs.append(cs[j] + p[j])
	dista = [-1] * (n + 1)
	d = deque([a])
	dista[a] = 0
	while d:
		temp = d.popleft()
		for edge in connected[temp]:
			if dista[edge] == -1:
				d.append(edge)
				dista[edge] = dista[temp] + 1
	d.append(b)
	distb = [-1] * (n + 1)
	distb[b] = 0
	while d:
		temp = d.popleft()
		for edge in connected[temp]:
			if distb[edge] == -1:
				d.append(edge)
				distb[edge] = distb[temp] + 1
	d.append(c)
	distc = [-1] * (n + 1)
	distc[c] = 0
	while d:
		temp = d.popleft()
		for edge in connected[temp]:
			if distc[edge] == -1:
				d.append(edge)
				distc[edge] = distc[temp] + 1
	ans = float('inf')
	for j in range(1, n + 1):
		distsum = dista[j] + distb[j] + distc[j]
		if distsum <= m:
			ans = min(ans, cs[distsum] + cs[distb[j]])
	print(ans)


def call(x, n):
	q = deque()
	q.append(x)
	vis = [-1] * (n + 1)
	vis[x] = 0
	while q:
		v = q.popleft()
		for i in gr[v]:
			if vis[i] == -1:
				vis[i] = vis[v] + 1
				q.append(i)
	return vis
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
from collections import deque
from itertools import accumulate
gr = defaultdict(list)
import math
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	for _ in range(m):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	v1 = call(a, n)
	v2 = call(b, n)
	v3 = call(c, n)
	p = [0] + list(accumulate(p))
	ans = math.inf
	for x in range(1, n + 1):
		if v1[x] + v2[x] + v3[x] <= m:
			ans = min(ans, p[v2[x]] + p[v1[x] + v2[x] + v3[x]])
	print(ans)
	gr.clear()


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
from heapq import heappop as po
from heapq import heappush as pu
t = int(input())
inf = float('INF')
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c -= 1
	gr = [[] for i in range(n)]
	p = list(map(int, input().split()))
	p.sort()
	for i in range(m):
		(u, v) = map(int, input().split())
		gr[u - 1].append(v - 1)
		gr[v - 1].append(u - 1)
	pa = {i: i for i in range(n)}
	ca = {i: inf for i in range(n)}
	pa[a] = -1
	ca[a] = 0
	q = [(0, a)]
	while q:
		(v, x) = po(q)
		for y in gr[x]:
			if y == pa[x]:
				continue
			if v + 1 < ca[y]:
				ca[y] = v + 1
				pu(q, (v + 1, y))
				pa[y] = x
	pb = {i: i for i in range(n)}
	cb = {i: inf for i in range(n)}
	pb[b] = -1
	cb[b] = 0
	q = [(0, b)]
	while q:
		(v, x) = po(q)
		for y in gr[x]:
			if y == pb[x]:
				continue
			if v + 1 < cb[y]:
				cb[y] = v + 1
				pu(q, (v + 1, y))
				pb[y] = x
	pc = {i: i for i in range(n)}
	cc = {i: inf for i in range(n)}
	pc[c] = -1
	cc[c] = 0
	q = [(0, c)]
	while q:
		(v, x) = po(q)
		for y in gr[x]:
			if y == pc[x]:
				continue
			if v + 1 < cc[y]:
				cc[y] = v + 1
				pu(q, (v + 1, y))
				pc[y] = x
	pp = [p[0]]
	for i in range(1, m):
		pp.append(pp[-1] + p[i])
	pp.append(0)
	ans = inf
	for x in range(n):
		if ca[x] + cc[x] + cb[x] - 1 < m:
			ans = min(ans, pp[cb[x] - 1] + pp[ca[x] + cc[x] + cb[x] - 1])
	print(ans)


from collections import deque
import sys
input = sys.stdin.readline

def solve():
	(n, m, a, b, c) = map(int, input().split())
	Price = list(map(int, input().split()))
	G = [[] for i in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	Price.sort()
	sumPrice = [0] * (m + 1)
	for i in range(m):
		sumPrice[i + 1] = sumPrice[i] + Price[i]

	def bfs(S):
		visited = [False] * (n + 1)
		dis = [0] * (n + 1)
		que = deque([S])
		visited[S] = True
		while que:
			x = que.popleft()
			for c in G[x]:
				if visited[c] == False:
					dis[c] = dis[x] + 1
					visited[c] = True
					que.append(c)
		return dis
	dist_a = bfs(a)
	dist_b = bfs(b)
	dist_c = bfs(c)
	ans = 10 ** 30
	for i in range(1, n + 1):
		(x, y, z) = (dist_a[i], dist_b[i], dist_c[i])
		if x + y + z > m:
			continue
		else:
			ans = min(ans, sumPrice[y] + sumPrice[x + y + z])
	print(ans)
	return

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().split()]

def st():
	return input()

def val():
	return int(input())

def li2():
	return [i for i in input()]

def li3():
	return [int(i) for i in input()]
d = defaultdict(set)
n = m = 0

def dfs(a):
	global d, m, n
	l = [0] * (n + 1)
	visited = {}
	q = deque([[a, 0]])
	while q:
		(root, dis) = q.popleft()
		if root in visited:
			continue
		l[root] = dis
		visited[root] = 1
		for j in d[root]:
			if j not in visited:
				q.append([j, dis + 1])
	return l[:]
for _ in range(val()):
	(n, m, a, b, c) = li()
	p = sorted(li())
	d = defaultdict(set)
	for i in range(m):
		(x, y) = li()
		d[x].add(y)
		d[y].add(x)
	l1 = dfs(a)
	l2 = dfs(b)
	l3 = dfs(c)
	ans = float('inf')
	prefsum = [0]
	for i in p:
		prefsum.append(prefsum[-1] + i)
	for i in range(1, n + 1, 1):
		if l1[i] + l2[i] + l3[i] > m:
			continue
		ans = min(ans, prefsum[l1[i] + l2[i] + l3[i]] + prefsum[l2[i]])
	print(ans)


import sys
import io, os
import math
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import collections
from collections import defaultdict

def bfs1(root):
	queue = collections.deque([root])
	dist = [math.inf] * (n + 1)
	dist[root] = 0
	while queue:
		vertex = queue.popleft()
		for neighbour in graph1[vertex]:
			if dist[neighbour] != math.inf:
				continue
			dist[neighbour] = min(dist[neighbour], dist[vertex] + 1)
			queue.append(neighbour)
	return dist

def restore(par, s, src):
	res = []
	while s != src:
		res.append(par[s][1])
		s = par[s][0]
	return res
t = int(input())
for count in range(t):
	(n, m, a, b, c) = map(int, input().split())
	p = [int(i) for i in input().split() if i != '\n']
	p.sort()
	p.insert(0, 0)
	for i in range(1, len(p)):
		p[i] = p[i - 1] + p[i]
	graph1 = defaultdict(list)
	for j in range(m):
		(x, y) = map(int, input().split())
		graph1[x].append(y)
		graph1[y].append(x)
	one = bfs1(a)
	two = bfs1(b)
	three = bfs1(c)
	ans = math.inf
	for i in range(1, len(three)):
		try:
			ans = min(ans, p[one[i] + two[i] + three[i]] + p[two[i]])
		except:
			pass
	sys.stdout.write(str(ans) + '\n')


from collections import deque
from itertools import accumulate
from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m, a, b, c) = [int(x) for x in stdin.readline().split()]
	p = list(accumulate([0, *sorted((int(x) for x in stdin.readline().split())), *(10 ** 9 for i in range(3 * n - 3 - m))]))
	adj = [[] for i in range(n + 1)]
	for e in range(m):
		(u, v) = [int(x) for x in stdin.readline().split()]
		adj[u].append(v)
		adj[v].append(u)
	da = [-1 for i in range(n + 1)]
	db = [-1 for i in range(n + 1)]
	dc = [-1 for i in range(n + 1)]
	for (s, d) in ((a, da), (b, db), (c, dc)):
		q = deque([s])
		d[s] = 0
		while len(q) > 0:
			u = q.popleft()
			for v in adj[u]:
				if d[v] == -1:
					d[v] = d[u] + 1
					q.append(v)

	def rsq(L, R):
		return p[R] - p[L - 1]
	print(min((2 * rsq(1, db[x]) + rsq(db[x] + 1, db[x] + da[x] + dc[x]) for x in range(1, n + 1))))


import os, sys
from io import BytesIO, IOBase
from collections import deque
INF = float('inf')

def getdistance(node, path, n):
	dis = [INF] * (n + 1)
	(dis[node], curr) = (0, deque([node]))
	while len(curr):
		x = curr.popleft()
		for y in path[x]:
			if dis[y] == INF:
				dis[y] = dis[x] + 1
				curr.append(y)
	return dis

def main():
	for _ in range(int(input())):
		(n, m, a, b, c) = map(int, input().split())
		price = [0] + sorted(map(float, input().split()))
		for i in range(1, m + 1):
			price[i] += price[i - 1]
		path = [[] for _ in range(n + 1)]
		for _ in range(m):
			(u1, v1) = map(int, input().split())
			path[u1].append(v1)
			path[v1].append(u1)
		disa = getdistance(a, path, n)
		disb = getdistance(b, path, n)
		disc = getdistance(c, path, n)
		ans = INF
		for i in range(1, n + 1):
			z = disa[i] + disb[i] + disc[i]
			if z <= m:
				ans = min(ans, price[disb[i]] + price[z])
		print(int(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def bfs(start):
	inf = float('inf')
	dist = [inf] * (n + 1)
	q = deque()
	dist[start] = 0
	q.append(start)
	while q:
		node = q.popleft()
		for child in g[node]:
			if dist[child] == inf:
				dist[child] = dist[node] + 1
				q.append(child)
	return dist
for _ in range(iinput()):
	(n, m, a, b, c) = rinput()
	val = list(accumulate(sorted(rlinput() + [0])))
	g = defaultdict(list)
	for i in range(m):
		(u, v) = rinput()
		g[u].append(v)
		g[v].append(u)
	d1 = bfs(a)
	d2 = bfs(b)
	d3 = bfs(c)
	ans = float('inf')
	for i in range(1, n + 1):
		s = d1[i] + d2[i] + d3[i]
		if s <= m:
			ans = min(ans, val[s] + val[d2[i]])
	print(ans)


from sys import stdin
from itertools import accumulate
from collections import deque

def bfs(r, pr, tp):
	global g, d
	q = deque([r])
	d[tp][r] = d[tp][pr] + 1
	while len(q) > 0:
		pr = q.popleft()
		for r in g[pr]:
			if d[tp][r] != -1:
				continue
			d[tp][r] = d[tp][pr] + 1
			q.append(r)
for _ in range(int(input())):
	(n, m, a, b, c) = map(int, stdin.readline().split())
	p = list(accumulate(sorted(map(int, stdin.readline().split()))))
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, stdin.readline().split())
		g[u].append(v)
		g[v].append(u)
	d = [[-1 for x in range(n + 1)] for i in range(3)]
	bfs(a, a, 0)
	bfs(b, b, 1)
	bfs(c, c, 2)
	p.append(0)
	print(min([p[d[0][x] + d[1][x] + d[2][x] - 1] + p[d[1][x] - 1] for x in range(1, n + 1) if d[0][x] + d[1][x] + d[2][x] - 1 < m]))


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def bfs(u):
		q = deque([u])
		res = [-1] * n
		res[u] = 0
		while q:
			u = q.popleft()
			for v in to[u]:
				if res[v] != -1:
					continue
				res[v] = res[u] + 1
				q.append(v)
		return res
	for _ in range(II()):
		(n, m, a, b, c) = MI()
		(a, b, c) = (a - 1, b - 1, c - 1)
		pp = LI()
		to = [[] for _ in range(n)]
		for _ in range(m):
			(u, v) = MI1()
			to[u].append(v)
			to[v].append(u)
		dist = []
		for u in [a, b, c]:
			dist.append(bfs(u))
		cs = [0]
		for p in sorted(pp):
			cs.append(cs[-1] + p)
		ans = 10 ** 16
		for u in range(n):
			d = dist[0][u] + dist[1][u] + dist[2][u]
			if d > m:
				continue
			cur = cs[d] + cs[dist[1][u]]
			if cur < ans:
				ans = cur
		print(ans)
main()


import collections
t = int(input())

def bfs(start):
	dist = [-1 for j in range(n)]
	dist[start] = 0
	q = collections.deque([start])
	while q:
		node = q.popleft()
		for nei in graph[node]:
			if dist[nei] < 0:
				dist[nei] = dist[node] + 1
				q.append(nei)
	return dist
for i in range(t):
	(n, m, a, b, c) = map(int, input().split())
	graph = collections.defaultdict(list)
	price = [int(j) for j in input().split()]
	price.sort()
	fp = [0 for j in range(m + 1)]
	for j in range(1, m + 1):
		fp[j] = fp[j - 1] + price[j - 1]
	for j in range(m):
		(n1, n2) = map(int, input().split())
		graph[n1 - 1].append(n2 - 1)
		graph[n2 - 1].append(n1 - 1)
	path1 = bfs(a - 1)
	path2 = bfs(b - 1)
	path3 = bfs(c - 1)
	output = float('inf')
	for j in range(n):
		if path1[j] + path2[j] + path3[j] > m:
			continue
		output = min(output, fp[path2[j]] + fp[path1[j] + path2[j] + path3[j]])
	print(output)


from collections import *
from bisect import *
import sys
input = sys.stdin.readline

def bfs(cur, gr, vis):
	f = []
	f = deque(f)
	f.append(cur)
	vis[f[0]] = 1
	di = [0 for i in range(len(vis))]
	while len(f):
		rf = f.popleft()
		for i in range(len(gr[rf])):
			if vis[gr[rf][i]] == 0:
				f.append(gr[rf][i])
				di[gr[rf][i]] = di[rf] + 1
				vis[gr[rf][i]] = 1
	return di
t = int(input())
while t:
	t -= 1
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	pre = [0, p[0]]
	for i in range(1, m):
		pre.append(p[i] + pre[-1])
	gr = [[] for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	da = bfs(a, gr, vis[:])
	db = bfs(b, gr, vis[:])
	dc = bfs(c, gr, vis[:])
	r = float('inf')
	for i in range(1, n + 1):
		try:
			r = min(r, pre[db[i]] + pre[da[i] + db[i] + dc[i]])
		except:
			pass
	print(r)


import sys
input = sys.stdin.readline
INF = 10 ** 16
Q = int(input())
Query = []
for _ in range(Q):
	(N, M, a, b, c) = map(int, input().split())
	P = list(map(int, input().split()))
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	Query.append((N, M, a - 1, b - 1, c - 1, P, graph))

def bfs(s, N, graph):
	q = [s]
	D = [-1] * N
	D[s] = 0
	while q:
		qq = []
		for p in q:
			for np in graph[p]:
				if D[np] == -1:
					D[np] = D[p] + 1
					qq.append(np)
		q = qq
	return D
for (N, M, a, b, c, P, graph) in Query:
	Da = bfs(a, N, graph)
	Db = bfs(b, N, graph)
	Dc = bfs(c, N, graph)
	P.sort()
	W = [0]
	for p in P:
		W.append(W[-1] + p)
	ans = INF
	for n in range(N):
		da = Da[n]
		db = Db[n]
		dc = Dc[n]
		if da + db + dc > M:
			continue
		score = W[db] + W[da + db + dc]
		if score < ans:
			ans = score
	print(ans)


import sys
input = sys.stdin.buffer.readline
from collections import deque
from itertools import accumulate

def main():
	t = int(input())
	for _ in range(t):
		(n, m, a, b, c) = map(int, input().split())
		(a, b, c) = (a - 1, b - 1, c - 1)
		P = list(map(int, input().split()))
		P.sort()
		g = [[] for i in range(n)]
		for i in range(m):
			(v, u) = map(int, input().split())
			(v, u) = (v - 1, u - 1)
			g[v].append(u)
			g[u].append(v)

		def bfs(s):
			q = deque()
			visit = [-1] * n
			q.append(s)
			visit[s] = 0
			while q:
				v = q.popleft()
				for u in g[v]:
					if visit[u] == -1:
						visit[u] = visit[v] + 1
						q.append(u)
			return visit
		visit1 = bfs(a)
		visit2 = bfs(b)
		visit3 = bfs(c)
		C = [0] + P
		C = list(accumulate(C))
		ans = 10 ** 18
		for i in range(n):
			if visit1[i] + visit2[i] + visit3[i] > m:
				continue
			ans = min(ans, C[visit2[i]] + C[visit1[i] + visit2[i] + visit3[i]])
		print(ans)
main()


from functools import cmp_to_key
from collections import deque
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def sli():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)

def custom_sort(lista):

	def cmp(x, y):
		if x + y > y + x:
			return 1
		else:
			return -1
	return sorted(lista, key=cmp_to_key(cmp))
MOD = 10 ** 9 + 7
maxN = 10 ** 5
FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def coeffBinom(n, k):
	if n < k:
		return 0
	return divide(FACT[n], multiply(FACT[k], FACT[n - k]))

def primes(N):
	smallest_prime = [1] * (N + 1)
	prime = []
	smallest_prime[0] = 0
	smallest_prime[1] = 0
	for i in range(2, N + 1):
		if smallest_prime[i] == 1:
			prime.append(i)
			smallest_prime[i] = i
		j = 0
		while j < len(prime) and i * prime[j] <= N:
			smallest_prime[i * prime[j]] = min(prime[j], smallest_prime[i])
			j += 1
	return (prime, smallest_prime)

def gcd(a, b):
	a = abs(a)
	b = abs(b)
	(s, t, r) = (0, 1, b)
	(old_s, old_t, old_r) = (1, 0, a)
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return (old_r, old_s, old_t)

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def create_edges(m, unweighted=0):
	edges = list()
	if unweighted:
		for i in range(m):
			edges.append(li(lag=-1))
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			edges.append([w, x, y])
	return edges

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def connected(graph, n):
	v = dfs(graph, n, 0)
	for el in v:
		if el == -1:
			return False
	return True

def topological(graph, n):
	indegree = [0] * n
	for el in range(n):
		for child in graph[el]:
			indegree[child] += 1
	s = deque()
	for el in range(n):
		if indegree[el] == 0:
			s.append(el)
	order = []
	while s:
		el = s.popleft()
		order.append(el)
		for child in graph[el]:
			indegree[child] -= 1
			if indegree[child] == 0:
				s.append(child)
	if n == len(order):
		return (False, order)
	else:
		return (True, [])

def bipartite(graph, n):
	color = [-1] * n
	color[0] = 0
	s = [0]
	while s:
		el = s.pop()
		for child in graph[el]:
			if color[child] == color[el]:
				return False
			if color[child] == -1:
				s.append(child)
			color[child] = 1 - color[el]
	return True

def dijkstra(graph, n, A):
	dist = [float('inf') for i in range(n)]
	prev = [-1 for i in range(n)]
	dist[A] = 0
	pq = []
	heappush(pq, [0, A])
	while pq:
		[d_v, v] = heappop(pq)
		if d_v != dist[v]:
			continue
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
				prev[to] = v
				heappush(pq, [dist[to], to])
	return (dist, prev)

def dijkstra_0_1(graph, n, A):
	dist = [float('inf') for i in range(n)]
	dist[A] = 0
	p = deque()
	p.append(A)
	while p:
		v = p.popleft()
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
			if w == 1:
				q.append(to)
			else:
				q.appendleft(to)
	return dist

def floyd_warshall(graph, n):
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for (child, d) in graph[i]:
			dist[i][child] = d
			dist[child][i] = d
	for k in range(n):
		for i in range(n):
			for j in range(j):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

def minimum_spanning_tree(edges, n):
	edges = sorted(edges)
	union_find = UnionFind(n)
	used_edges = list()
	for (w, x, y) in edges:
		if union_find.find(x) != union_find.find(y):
			union_find.merge(x, y)
			used_edges.append([w, x, y])
	return used_edges

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def finding_ancestors(parent, queries, n):
	steps = int(ceil(log(n, 2)))
	ancestors = [[-1 for i in range(n)] for j in range(steps)]
	ancestors[0] = parent
	for i in range(1, steps):
		for node in range(n):
			if ancestors[i - 1][node] != -1:
				ancestors[i][node] = ancestors[i - 1][ancestors[i - 1][node]]
	result = []
	for (node, k) in queries:
		ans = node
		if k >= n:
			ans = -1
		i = 0
		while k > 0 and ans != -1:
			if k % 2:
				ans = ancestors[i][ans]
			k = k // 2
			i += 1
		result.append(ans)
	return result

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def nearest_from_the_left_smaller_elements(arr):
	n = len(arr)
	res = [-1] * n
	s = []
	for (i, el) in enumerate(arr):
		while s and s[-1] >= el:
			s.pop()
		if s:
			res[i] = s[-1]
		s.append(el)
	return res

def sliding_window_minimum(arr, k):
	res = []
	q = deque()
	for (i, el) in enumerate(arr):
		while q and arr[q[-1]] >= el:
			q.pop()
		q.append(i)
		while q and q[0] <= i - k:
			q.popleft()
		if i >= k - 1:
			res.append(arr[q[0]])
	return res
for test in range(ii()):
	[n, m, a, b, c] = li()
	p = sorted(li())
	pre = [0]
	for i in range(m):
		pre.append(pre[-1] + p[i])
	(a, b, c) = (a - 1, b - 1, c - 1)
	graph = create_graph(n, m)
	(da, db, dc) = (bfs(graph, n, a), bfs(graph, n, b), bfs(graph, n, c))
	mi = float('inf')
	for i in range(n):
		if db[i] + da[i] + dc[i] > m:
			continue
		x = pre[db[i]]
		y = pre[db[i] + da[i] + dc[i]]
		mi = min(mi, x + y)
	print(mi)


from sys import stdin, gettrace
from collections import deque

def input():
	return stdin.buffer.readline()

def readGraph(n, m):
	adj = [set() for i in range(n + 1)]
	for i in range(m):
		(v1, v2) = [int(x) for x in input().split()]
		adj[v1].add(v2)
		adj[v2].add(v1)
	return adj

def bfs(adj, src, n):
	q = deque()
	q.append(src)
	visited = [False] * (n + 1)
	distance = [0] * (n + 1)
	visited[src] = True
	while q:
		ele = q.popleft()
		for a in adj[ele]:
			if visited[a] == False:
				q.append(a)
				distance[a] = distance[ele] + 1
				visited[a] = True
	return distance

def solve():
	(n, m, a, b, c) = [int(x) for x in input().split()]
	p = [0] + [int(x) for x in input().split()]
	adj = readGraph(n, m)
	dA = bfs(adj, a, n)
	dB = bfs(adj, b, n)
	dC = bfs(adj, c, n)
	p.sort()
	psum = [0] * (m + 1)
	psum[1] = p[0]
	for i in range(1, m + 1):
		psum[i] = psum[i - 1] + p[i]
	pay = 99999999999999
	for D in range(1, n + 1):
		DA = dA[D]
		DB = dB[D]
		DC = dC[D]
		if DA + DB + DC <= m:
			pay = min(pay, psum[DB] + psum[DA + DB + DC])
	print(pay)
	return

def main():
	q = int(input())
	for _ in range(q):
		solve()
main()


from sys import stdin
import sys
from collections import deque

def bfs(x, d):
	d[x] = 0
	q = deque()
	q.append(x)
	while len(q) != 0:
		z = q.popleft()
		for i in dictt[z]:
			if d[i] == mm:
				d[i] = d[z] + 1
				q.append(i)
mm = 100000000000000000000
for _ in range(int(stdin.readline())):
	(n, m, a, b, c) = map(int, stdin.readline().split())
	a -= 1
	b -= 1
	c -= 1
	p = sorted(list(map(int, stdin.readline().split())))
	dictt = {}
	for i in range(m):
		(u, v) = map(int, stdin.readline().split())
		if u - 1 in dictt:
			dictt[u - 1].append(v - 1)
		else:
			dictt[u - 1] = [v - 1]
		if v - 1 in dictt:
			dictt[v - 1].append(u - 1)
		else:
			dictt[v - 1] = [u - 1]
	pref = [0] * (m + 1)
	pref[0] = 0
	for i in range(1, m + 1):
		pref[i] = pref[i - 1] + p[i - 1]
	da = [mm] * n
	db = [mm] * n
	dc = [mm] * n
	bfs(a, da)
	bfs(b, db)
	bfs(c, dc)
	ans = mm
	for i in range(n):
		if da[i] + db[i] + dc[i] > m:
			continue
		ans = min(ans, pref[db[i]] + pref[da[i] + db[i] + dc[i]])
	print(ans)


import sys
input = sys.stdin.readline
from collections import deque

def bfs(node):
	dist = [float('inf')] * (len(graph) + 1)
	queue = deque([node])
	dist[node] = 0
	while queue:
		node = queue.popleft()
		for n in graph[node]:
			if dist[n] > dist[node] + 1:
				dist[n] = dist[node] + 1
				queue.append(n)
	return dist
for _ in range(int(input())):
	(n, m, a, b, c) = map(int, input().split())
	p = list(map(int, input().split()))
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	da = bfs(a)
	db = bfs(b)
	dc = bfs(c)
	ans = float('inf')
	p.sort()
	pre = [0]
	for i in p:
		pre.append(pre[-1] + i)
	for i in range(1, n + 1):
		(d1, d2, d3) = (da[i], db[i], dc[i])
		if d1 + d2 + d3 > m:
			continue
		ans = min(pre[d1 + d2 + d3] + pre[d2], ans)
	print(ans)


from collections import deque
import os
import sys
from io import BytesIO, IOBase

def bfs(G, distance, start):
	V = set()
	V.add(start)
	Q = deque([start])
	while Q:
		node = Q.popleft()
		for v in G[node]:
			if v not in V:
				V.add(v)
				distance[v] = distance[node] + 1
				Q.append(v)

def main():
	T = int(input())
	for _ in range(T):
		(n, m, a, b, c) = map(int, input().split())
		P = list(map(int, input().split()))
		G = dict()
		for i in range(m):
			(u, v) = map(int, input().split())
			if u not in G:
				G[u] = list()
			if v not in G:
				G[v] = list()
			G[u].append(v)
			G[v].append(u)
		P.sort()
		prefix = [0] * (m + 1)
		for i in range(1, m + 1):
			prefix[i] = prefix[i - 1] + P[i - 1]
		bfsA = [0] * (n + 1)
		bfsB = [0] * (n + 1)
		bfsC = [0] * (n + 1)
		bfs(G, bfsA, a)
		bfs(G, bfsB, b)
		bfs(G, bfsC, c)
		cost = [None] * (n + 1)
		for x in range(1, n + 1):
			unrep = bfsA[x] + bfsC[x]
			rep = bfsB[x]
			if unrep + rep > m:
				cost[x] = None
			else:
				cost[x] = prefix[rep] * 2 + (prefix[unrep + rep] - prefix[rep])
		m = None
		for c in cost:
			if c is not None:
				if m is None:
					m = c
				else:
					m = min(m, c)
		print(m)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = lambda s: self.buffer.write(s.encode()) if self.writable else None

	def read(self):
		if self.buffer.tell():
			return self.buffer.read().decode('ascii')
		return os.read(self._fd, os.fstat(self._fd).st_size).decode('ascii')

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline().decode('ascii')

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

def print(*args, sep=' ', end='\n', file=sys.stdout, flush=False):
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(end)
	if flush:
		file.flush()
(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10000)
main()


import sys
from collections import deque
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	p.sort()
	pref = [0]
	curr = 0
	for i in range(m):
		curr += p[i]
		pref.append(curr)
	adj = [[] for i in range(n)]
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	aD = [-1] * n
	bD = [-1] * n
	cD = [-1] * n
	for i in range(3):
		q = deque()
		q.append(([a, b, c][i] - 1, 0))
		l = [aD, bD, cD][i]
		l[q[0][0]] = 0
		while q:
			(v, d) = q.popleft()
			for nex in adj[v]:
				if l[nex] == -1:
					l[nex] = d + 1
					q.append((nex, d + 1))
	poss = []
	for i in range(n):
		if aD[i] + bD[i] + cD[i] <= m:
			poss.append(pref[aD[i] + bD[i] + cD[i]] + pref[bD[i]])
	print(min(poss))


import sys
input = sys.stdin.buffer.readline
for f in range(int(input())):
	(n, m, x, y, z) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	x -= 1
	y -= 1
	z -= 1
	neig = [0] * n
	dx = [-1] * n
	dy = [-1] * n
	dz = [-1] * n
	dx[x] = 0
	dy[y] = 0
	dz[z] = 0
	levx = [[x]]
	levy = [[y]]
	levz = [[z]]
	for i in range(n):
		neig[i] = [0]
	for i in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		neig[a][0] += 1
		neig[b][0] += 1
		neig[a].append(b)
		neig[b].append(a)
	i = 0
	while i < len(levx):
		toad = []
		for v in levx[i]:
			for j in range(1, neig[v][0] + 1):
				u = neig[v][j]
				if dx[u] == -1:
					dx[u] = i + 1
					toad.append(u)
		if len(toad) > 0:
			levx.append(toad)
		i += 1
	i = 0
	while i < len(levy):
		toad = []
		for v in levy[i]:
			for j in range(1, neig[v][0] + 1):
				u = neig[v][j]
				if dy[u] == -1:
					dy[u] = i + 1
					toad.append(u)
		if len(toad) > 0:
			levy.append(toad)
		i += 1
	i = 0
	while i < len(levz):
		toad = []
		for v in levz[i]:
			for j in range(1, neig[v][0] + 1):
				u = neig[v][j]
				if dz[u] == -1:
					dz[u] = i + 1
					toad.append(u)
		if len(toad) > 0:
			levz.append(toad)
		i += 1
	pt = [0] * m
	for i in range(m):
		pt[i] = pt[i - 1] + p[i]
	mi = 2 * pt[m - 1]
	for i in range(n):
		m1 = dx[i] + dy[i] + dz[i]
		if m1 <= m:
			mix = 0
			if m1 > 0:
				mix += pt[m1 - 1]
			if dy[i] > 0:
				mix += pt[dy[i] - 1]
			mi = min(mix, mi)
	print(mi)


import io
import os
from collections import Counter, defaultdict, deque

def bfs(source, graph):
	q = deque([source])
	dist = {source: 0}
	while q:
		node = q.popleft()
		d = dist[node]
		for nbr in graph[node]:
			if nbr not in dist:
				dist[nbr] = d + 1
				q.append(nbr)
	return dist

def solve(N, M, A, B, C, P, edges):
	cumsum = [0]
	P.sort()
	for x in P:
		cumsum.append(cumsum[-1] + x)
	graph = [[] for i in range(N + 1)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	aDist = bfs(A, graph)
	bDist = bfs(B, graph)
	cDist = bfs(C, graph)
	best = float('inf')
	for u in range(1, N + 1):
		treeLen = aDist[u] + bDist[u] + cDist[u]
		repeatLen = bDist[u]
		if treeLen < len(cumsum) and repeatLen < len(cumsum):
			cost = cumsum[aDist[u] + bDist[u] + cDist[u]] + cumsum[bDist[u]]
			best = min(best, cost)
	return best
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N, M, A, B, C) = [int(x) for x in input().split()]
	P = [int(x) for x in input().split()]
	edges = [[int(x) for x in input().split()] for i in range(M)]
	ans = solve(N, M, A, B, C, P, edges)
	print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def solve():
	(n, m, a, b, c) = sep()
	g = [[] for _ in range(n + 1)]
	path = lis()
	for _ in range(m):
		(i, j) = sep()
		g[i].append(j)
		g[j].append(i)
	inf = float('inf')
	dista = [inf] * (n + 1)
	distb = [inf] * (n + 1)
	distc = [inf] * (n + 1)
	q = deque([(a, 0)])
	visited = set()
	visited.add(a)
	while q:
		(v, d) = q.popleft()
		dista[v] = d
		for ch in g[v]:
			if ch not in visited:
				visited.add(ch)
				q.append((ch, d + 1))
	q = deque([(b, 0)])
	visited = set()
	visited.add(b)
	while q:
		(v, d) = q.popleft()
		distb[v] = d
		for ch in g[v]:
			if ch not in visited:
				visited.add(ch)
				q.append((ch, d + 1))
	q = deque([(c, 0)])
	visited = set()
	visited.add(c)
	while q:
		(v, d) = q.popleft()
		distc[v] = d
		for ch in g[v]:
			if ch not in visited:
				visited.add(ch)
				q.append((ch, d + 1))
	path.sort()
	pa = [0] + prefix_sum(path)
	mi = inf
	for i in range(1, n + 1):
		B = distb[i]
		A = dista[i]
		C = distc[i]
		if B + A + C > m:
			continue
		ABCp = pa[A + C + B] + pa[B]
		mi = min(mi, ABCp)
	print(mi)
testcase(int(inp()))


import sys
from collections import deque

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 6
t = int(input())
for _ in range(t):
	(n, m, a, b, c) = map(int, input().split())
	(a, b, c) = (a - 1, b - 1, c - 1)
	p = list(map(int, input().split()))
	p.sort()
	cum = [0 for _ in range(m + 1)]
	for (i, x) in enumerate(p):
		cum[i + 1] = cum[i] + x
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	(a_dist, b_dist, c_dist) = ([INF for _ in range(n)], [INF for _ in range(n)], [INF for _ in range(n)])
	a_dist[a] = 0
	q = deque([a])
	while q:
		l = q.popleft()
		for v in adj[l]:
			if a_dist[v] > a_dist[l] + 1:
				a_dist[v] = a_dist[l] + 1
				q.append(v)
	b_dist[b] = 0
	q = deque([b])
	while q:
		l = q.popleft()
		for v in adj[l]:
			if b_dist[v] > b_dist[l] + 1:
				b_dist[v] = b_dist[l] + 1
				q.append(v)
	c_dist[c] = 0
	q = deque([c])
	while q:
		l = q.popleft()
		for v in adj[l]:
			if c_dist[v] > c_dist[l] + 1:
				c_dist[v] = c_dist[l] + 1
				q.append(v)
	ans = 10 ** 20
	for i in range(n):
		(aa, bb, cc) = (a_dist[i], b_dist[i], c_dist[i])
		if aa + bb + cc > m:
			continue
		ans = min(ans, cum[aa + bb + cc] + cum[bb])
	print(ans)


from sys import stdin
import math
from collections import deque
from bisect import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')

def getPath(root):
	dis = [None] * (n + 1)
	d = deque([root])
	dis[root] = 0
	cnt = 0
	while d:
		cnt += 1
		for _ in range(len(d)):
			p = d.popleft()
			for c in adj[p]:
				if dis[c] is None:
					d.append(c)
					dis[c] = cnt
	return dis
(t,) = gil()
for _ in range(t):
	(n, m, a, b, c) = gil()
	p = gil()
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = gil()
		adj[x].append(y)
		adj[y].append(x)
	p.sort()
	for i in range(1, m):
		p[i] += p[i - 1]
	p = [0] + p
	(da, db, dc) = (getPath(a), getPath(b), getPath(c))
	ans = inf
	for d in range(1, n + 1):
		tot = da[d] + db[d] + dc[d]
		if tot <= m:
			ans = min(ans, p[db[d]] + p[tot])
	print(ans)