В прекрасном кампусе Панда и его друзья собираются встретиться, чтобы вместе поесть. Им нравится проводить время вместе по дороге, ведь так они могут свободно общаться друг с другом.

Кампус моделируется как связный неориентированный граф с $n$ вершинами и $m$ рёбрами, имеющими длины. Место встречи — торговый центр, расположенный в вершине $1$. $k$ друзей стартуют из различных вершин и направляются в торговый центр. Все друзья движутся с одинаковой скоростью ($1$ единица расстояния в единицу времени) и могут менять направление движения в любой точке на ребре (см. пояснение к примеру).

Пусть $t_{\text{meet}}$ — самый ранний возможный момент времени, к которому все друзья могут добраться до торгового центра. Исходя из этого самого раннего времени встречи, для каждого друга в отдельности найдите максимальное суммарное время, которое он может провести в компании (это означает, что хотя бы один другой друг находится в точности в том же месте графа — в вершине или в точке на ребре) до финального сбора в торговом центре.

При рассмотрении конкретного друга $i$ маршруты и стратегии движения всех остальных друзей $j \neq i$ оптимизируются так, чтобы максимизировать время в компании для друга $i$, при условии что все друзья прибывают в торговый центр не позднее момента $t_{\text{meet}}$.

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

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

В каждом наборе входных данных первая строка содержит три целых числа $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), обозначающих количество вершин, рёбер и друзей соответственно.

Вторая строка содержит $k$ различных целых чисел $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), обозначающих стартовые вершины друзей.

Следующие $m$ строк содержат по три целых числа $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), описывающих ребро между вершинами $u$ и $v$ длины $w$. Граф связен и не содержит кратных рёбер и петель.

Сумма $n$ по всем наборам входных данных не превосходит $3 \times 10^5$, а сумма $m$ по всем наборам входных данных не превосходит $10^6$.

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

Для каждого набора входных данных выведите строку, содержащую $k$ вещественных чисел через пробел, каждое с ровно одним знаком после запятой, — максимальное время в компании для каждого друга.

Примеры

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

3
4 3 2
3 4
1 2 3
3 2 1
4 2 1
2 1 2
1 2
1 2 3
3 2 3
1 2 3
1 2 3
1 3 5

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

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Примечание

В третьем наборе входных данных из примера самое раннее время сбора в торговом центре равно $5$ единицам времени.

• Друзья из вершин $1$ и $2$ могут встретиться посередине ребра $(1, 2)$ через $1.5$ единицы времени, вместе вернуться в торговый центр ещё за $1.5$ единицы, а затем подождать $2$ единицы в торговом центре, проведя в компании в общей сложности $3.5$ единицы времени.
• Друг из вершины $3$ встречает друзей из вершины $1$ посередине ребра $(1, 3)$ через $2.5$ единицы времени и возвращается вместе с ними за $2.5$ единицы, проводя в компании в общей сложности $2.5$ единицы времени.