P4784 [BalticOI 2016] Cities (Day2)

In Byteland, there are $n$ cities, and among them there are $k$ major cities that the king often visits. There are $m$ roads, and each road connects two cities. Unfortunately, the poor condition of these roads prevents the king from driving at full speed. For each road, the repair cost is given. Your task is to selectively repair roads so that all $k$ major cities can be connected to each other using the repaired roads, while keeping the total cost as small as possible.

The first line contains three integers $n$, $k$, and $m$, representing the number of cities, the number of major cities, and the number of roads. The cities are numbered $1,2,\dots,n$. The second line contains $k$ integers, representing the major cities. The next $m$ lines each contain three integers $a$, $b$, and $c$, meaning there is a bidirectional road connecting city $a$ and city $b$, and the repair cost is $c$.

Output one line containing the minimum total cost that satisfies the above conditions.

For all subtasks, $1 \leq c \leq 10^9$ and $n \geq k$. |Subtask|Score|Constraints| |:-:|:-:|-| |1|22|$2 \leq k \leq 5,n \leq 20,1 \leq m \leq 40$| |2|14|$2 \leq k \leq 3,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$| |3|15|$2 \leq k \leq 4,n \leq 1000,1 \leq m \leq 2000$| |4|23|$k = 4,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$| |5|26|$k = 5,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$| Translated by ChatGPT 5