E1. Цифровая деревня (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. В трех версиях отличаются ограничения на $$$n$$$ и $$$m$$$. Вы можете совершать взломы только в том случае, если решены все версии задачи.

Пак Чанек устанавливает интернет-связь в деревне Кхунтиен. Деревню можно представить как связный простой граф с $$$n$$$ домами и $$$m$$$ интернет-кабелями, соединяющими дом $$$u_i$$$ и дом $$$v_i$$$, каждый с задержкой $$$w_i$$$.

Существует $$$p$$$ домов, которым требуется интернет. Пак Чанек может установить серверы не более чем в $$$k$$$ домов. Дома, которым нужен интернет, будут подключены к одному из серверов. Однако, поскольку каждый кабель имеет свою задержку, задержка, которую испытывает дом $$$s_i$$$, нуждающийся в интернете, будет равна максимальной задержке кабелей между этим домом и сервером, к которому он подключен.

Для каждого $$$k = 1,2,\ldots,n$$$, помогите Пак Чанеку определить минимальную суммарную задержку, которая может быть достигнута для всех домов, требующих интернет.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$, $$$p$$$ ($$$2 \le n \le 400$$$; $$$n-1 \le m \le 400$$$; $$$1 \le p \le n$$$) — количество домов, количество кабелей и количество домов, которым нужен интернет.

Вторая строка каждого набора входных данных содержит $$$p$$$ целых чисел $$$s_1, s_2, \ldots, s_p$$$ ($$$1 \le s_i \le n$$$) — номера домов, которым нужен интернет. Гарантируется, что все элементы $$$s$$$ различны.

В $$$i$$$-й из следующих $$$m$$$ строк каждого набора входных данных содержатся три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i < v_i \le n$$$; $$$1 \le w_i \le 10^9$$$) — интернет-кабель, соединяющий дом $$$u_i$$$ и дом $$$v_i$$$ с задержкой $$$w_i$$$. Гарантируется, что заданные ребра образуют простой связный граф.

Гарантируется, что сумма $$$n^3$$$ и сумма $$$m^3$$$ не превосходят $$$10^8$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел: минимальное общее время ожидания, которое может быть достигнуто для всех домов, нуждающихся в интернете для каждого $$$k = 1,2,\ldots,n$$$.

Пример
Входные данные
2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2
Выходные данные
34 19 9 4 0 0 0 0 0
2 0 0
Примечание

В первом наборе входных данных для $$$k=3$$$ одним из лучших решений является установка серверов в вершинах $$$2$$$, $$$6$$$ и $$$8$$$ и получение следующей задержки:

  • задержка$$$(2) = 0$$$
  • задержка$$$(5) = \max(3, 5) = 5$$$
  • задержка$$$(6) = 0$$$
  • задержка$$$(8) = 0$$$
  • задержка$$$(9) = \max(2, 4) = 4$$$

Таким образом, общая задержка составит $$$9$$$.