У чудовому кампусі Панда та його друзі домовилися зустрітися, щоб разом поїсти. Їм подобається проводити час разом дорогою, адже так вони можуть вільно спілкуватися одне з одним.

Кампус моделюється як зв'язний неорієнтований граф із $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$ одиниці часу в компанії.