E. Распределение весов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан неориентированный невзвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер (который представляет карту Бертауна), а также массив цен $$$p$$$ длины $$$m$$$. Гарантируется, что между каждой парой вершин (районов) существует путь.

Майк планирует совершить путешествие из вершины (района) $$$a$$$ в вершину (район) $$$b$$$, а затем из вершины (района) $$$b$$$ в вершину (район) $$$c$$$. Он может посещать один и тот же район дважды или даже большее число раз. Но есть небольшая проблема: власти города хотят ввести цену за использование дорог, таким образом, что если кто-то проходит по ней, то он должен заплатить цену, соответствующую этой дороге (он платит каждый раз, когда проходит по дороге). Список используемых цен $$$p$$$ готов и они просто хотят распределить его между всеми дорогами в городе таким образом, что каждая цена из массива соответствует ровно одной дороге.

Вы являетесь хорошим другом Майка (и, внезапно, мэром Бертауна) и хотите помочь сделать его путешествие настолько дешевым, насколько это возможно. Таким образом, ваша задача заключается в том, чтобы распределить цены между дорогами таким образом, что если Майк выберет оптимальный путь, то цена его путешествия будет минимально возможной. Заметьте, что вы не можете перераспределять цены после после начала путешествия.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $$$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(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$, $$$1 \le a, b, c \le n$$$) — количество вершин, количество ребер и районы в путешествии Майка.

Вторая строка набора тестовых данных содержит $$$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$$$).

Выходные данные

Выведите ответ на каждый набор тестовых данных — минимально возможную цену путешествия Майка, если вы распределите цены между ребрами оптимально.

Пример
Входные данные
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
Выходные данные
7
12
Примечание

Одно из возможных решение первого набора тестовых данных из примера:

Одно из возможных решение второго набора тестовых данных из примера: