У Эксбера есть неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. $$$i$$$-е ребро соединяет вершины $$$u_i$$$ и $$$v_i$$$ и имеет вес $$$w_i$$$.
Для любого пути пусть веса рёбер на нём образуют множество $$$S$$$; тогда длина этого пути определяется как $$$\operatorname{mex}(S)$$$. Здесь $$$\operatorname{mex}(S)$$$ обозначает наименьшее исключенное (MEX)$$$^{\text{∗}}$$$ набора чисел $$$S$$$. Пусть $$$\mathrm{dis}(u,v)$$$ обозначает минимальную длину пути среди всех путей, начинающихся в $$$u$$$ и заканчивающихся в $$$v$$$.
Теперь Эксбер хочет построить новый граф с $$$q$$$ вершинами. В новом графе цвет $$$i$$$-й вершины равен $$$c_i$$$. Изначально в этом графе нет рёбер. Если Эксбер добавляет ребро, соединяющее вершины $$$u$$$ и $$$v$$$, то это занимает $$$\mathrm{dis}(c_u,c_v)$$$ единиц времени. Если вершина $$$c_u$$$ и вершина $$$c_v$$$ не связаны в данном графике, Эксбер не может добавить край, соединяющий вершину $$$u$$$ и вершину $$$v$$$ в новом графике.
Определите минимальное количество времени, которое нужно потратить Эксберу, чтобы сделать новый граф связным.
$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$S_1, S_2, \ldots, S_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$S$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1\le n,m\le 3\cdot 10^5$$$, $$$1\le q\le n$$$) — количество вершин в графе, количество рёбер в графе и количество вершин в новом графе соответственно.
В следующих $$$m$$$ строках содержится по три целых числа $$$u$$$, $$$v$$$ и $$$w$$$ ($$$1\le u,v\le n$$$, $$$0\le w\le m$$$), означающих, что между вершинами $$$u$$$ и $$$v$$$ есть ребро веса $$$w$$$.
Следующая строка содержит $$$q$$$ целых чисел $$$c_i$$$ ($$$1\le c_i\le n$$$), означающих, что цвет вершины $$$i$$$ в новом графе равен $$$c_i$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.
Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.
Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество времени, которое нужно потратить Эксберу, чтобы сделать новый граф связным. Если это невозможно, выведите $$$-1$$$.
45 6 31 2 02 3 13 4 23 5 15 1 04 5 11 2 410 12 57 2 35 8 08 9 21 8 13 5 010 6 07 4 31 10 03 1 01 7 22 9 06 8 03 5 9 10 610 12 58 2 010 1 16 10 04 2 34 3 23 8 310 7 04 5 16 4 02 10 01 3 07 9 06 1 7 9 55 4 25 1 05 2 01 2 13 4 21 3
145-1
В первом наборе входных данных исходный граф содержит $$$5$$$ вершин и $$$5$$$ рёбер. Цвета вершин нового графа равны $$$1$$$, $$$2$$$ и $$$4$$$.
Исходный граф первого набора входных данных. Числа в скобках обозначают индексы вершин нового графа, цвет которых равен индексу данной вершины исходного графа. В новом графе Эксбер добавит рёбра $$$(1,2)$$$ и $$$(2,3)$$$, причём первое ребро будет стоить $$$1$$$ единицу времени, а второе — $$$0$$$ единиц времени; следовательно, суммарное время равно $$$1$$$.
Во втором наборе входных данных исходный граф содержит $$$10$$$ вершин и $$$12$$$ рёбер. Цвета вершин нового графа равны $$$3$$$, $$$5$$$, $$$9$$$, $$$10$$$ и $$$6$$$.
Исходный граф второго набора входных данных. Числа в скобках обозначают индексы вершин нового графа, цвет которых равен индексу данной вершины исходного графа. В новом графе Эксбер добавит рёбра $$$(1,2)$$$, $$$(2,3)$$$, $$$(3,4)$$$ и $$$(4,5)$$$, и каждое ребро будет стоить $$$1$$$ единицу времени; следовательно, суммарное время равно $$$4$$$.
