D. Максимальное расстояние
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Chouti устал от утомительного домашнего задания и решил открыть старую задачу, которую он придумал несколько лет назад.

Дан связный неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ взвешенных ребер. Также есть $$$k$$$ выделенных вершин: $$$x_1, x_2, \ldots, x_k$$$.

Определим стоимость пути как максимальный вес среди рёбер на пути, а расстояние между двумя вершинами как минимальную стоимость пути, их соединяющего.

Для каждой выделенной вершины найдите другую выделенную вершину, которая является максимально далёкой от неё (в терминах абзаца выше, то есть соответствующее расстояние максимально возможное), и выведите расстояние между ними.

Оригинальные ограничения очень маленькие, поэтому он подумал, что задача скучная. Теперь он увеличил ограничения и надеется, что вы можете решить эту задачу за него.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \leq k \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$).

Вторая строка содержит $$$k$$$ различных целых чисел $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \leq x_i \leq n$$$).

В каждой из следующих $$$m$$$ строк записаны по три целых числа $$$u$$$, $$$v$$$ и $$$w$$$ ($$$1 \leq u,v \leq n, 1 \leq w \leq 10^9$$$), задающие ребро между $$$u$$$ и $$$v$$$ веса $$$w$$$. Заданный граф — неориентированный, то есть каждое ребро $$$(u, v)$$$ может быть использовано в любом из двух направлений.

В графе могут содержаться кратные рёбра и петли.

Гарантируется, что граф является связным.

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

В единственной строке выведите $$$k$$$ целых чисел, где $$$i$$$-е из них должно равняться расстоянию между вершиной $$$x_i$$$ и самой далёкой от неё выделенной вершиной.

Примеры
Входные данные
2 3 2
2 1
1 2 3
1 2 2
2 2 1
Выходные данные
2 2
Входные данные
4 5 3
1 2 3
1 2 5
4 2 1
2 3 2
1 4 4
1 3 3
Выходные данные
3 3 3
Примечание

В первом примере, расстояние между вершинами $$$1$$$ и $$$2$$$ равно $$$2$$$, потому что можно пройти по ребру веса $$$2$$$, соединяющему их. Поэтому, расстояние до самой далекой точки от обеих вершин $$$1$$$ и $$$2$$$ равно $$$2$$$.

Во втором примере, расстояние между вершинами $$$1$$$ и $$$2$$$ и расстояние между вершинами $$$1$$$ и $$$3$$$ равны $$$3$$$, а расстояние между вершинами $$$2$$$ и $$$3$$$ равно $$$2$$$.

В графе могут содержаться параллельные ребра и петли, как в первом примере.