E. Встреча Мариан и Робина
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
В скромном акте встречи радость раскрывается, как цветок в цветении.

Отсутствие заставляет сердце тосковать. Мариан продала свой последний товар на рынке в то же время, когда Робин закончил тренировку у Великого Дуба. Они не могли дождаться встречи, поэтому оба отправились в путь без промедления.

Сеть путешествий представлена как $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ рёбер. $$$i$$$-е ребро соединяет вершины $$$v_i$$$ и $$$u_i$$$ и занимает $$$w_i$$$ секунд на преодоление (все $$$w_i$$$ четные). Мариан начинает с вершины $$$1$$$ (Рынок), а Робин начинает с вершины $$$n$$$ (Великий Дуб).

Кроме того, у $$$h$$$ из $$$n$$$ вершин есть по одному доступному коню. И Мариан, и Робин являются опытными всадниками и могут оседлать лошадей в считанные секунды (т.е. за $$$0$$$ секунд). Время в пути сокращается вдвое при езде на лошади. Как только они сядут на лошадь, она будет служить им на протяжении всего оставшегося пути. Встреча должна происходить на вершине (т.е. не на ребре). Каждый из них также может останавливаться в вершинах.

Выведите самое раннее время, когда Робин и Мариан могут встретиться. Если вершины $$$1$$$ и $$$n$$$ не соединены, выведите $$$-1$$$, так как встреча отменяется.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$, $$$h$$$ ($$$2 \le n \le 2 \cdot 10^5, \;1 \le m \le 2 \cdot 10^5, \; 1 \le h \le n$$$) — количество вершин, количество рёбер и количество вершин, в которых есть по одному коню.

Вторая строка каждого набора входных данных содержит $$$h$$$ различных целых чисел $$$a_1, a_2, \ldots, a_h$$$ ($$$1 \le a_i \le n$$$) — вершины, у которых есть по одному доступному коню.

Затем следуют $$$m$$$, каждая содержит по три целых числа $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1\le u_i,v_i \le n, \; 2\le w_i \le 10^6$$$) — что означает, что существует ребро между вершинами $$$u_i$$$ и $$$v_i$$$ с затратами на путешествие $$$w_i$$$ секунд без лошади.

Гарантируется, что суммы как $$$n$$$, так и $$$m$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

В графе нет петель и кратных рёбер, все $$$w_i$$$ являются четными целыми числами.

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

Для каждого набора входных данных выведите одно целое число — самое раннее время, когда Робин и Мариан могут встретиться. Если встреча невозможна, выведите $$$-1$$$.

Пример
Входные данные
6
2 1 1
1
1 2 10
3 1 2
2 3
1 2 10
3 3 1
2
1 2 4
1 3 10
2 3 6
4 3 2
2 3
1 2 10
2 3 18
3 4 16
3 2 1
2
1 2 4
1 3 16
7 7 1
3
1 5 2
2 6 12
1 2 12
6 4 8
7 3 4
6 3 4
7 6 4
Выходные данные
5
-1
6
19
14
12
Примечание

В первом наборе входных данных Мариан едет от вершины $$$1$$$ к вершине $$$2$$$, Робин ждет.

Во втором наборе входных данных вершины $$$1$$$ и $$$3$$$ не соединены.

В третьем наборе входных данных и Мариан, и Робин едут к вершине $$$2$$$, чтобы встретиться.

В четвертом наборе входных данных Мариан едет к вершине $$$2$$$ без лошади, оседлает лошадь на вершине $$$2$$$ и едет к вершине $$$3$$$, чтобы встретиться с Робином.

В пятом наборе входных данных Мариан едет к вершине $$$2$$$ без лошади, оседлает лошадь на вершине $$$2$$$ и возвращается к вершине $$$1$$$, а затем к вершине $$$3$$$.