Problem Description

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.

Input Format

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 Format

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

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

11

Hint

For all subtasks, $1 \leq c \leq 10^9$ and $n \geq k$.

Translated by ChatGPT 5