Description

There are $N$ cities, among which $K$ are occupied by enemy corps. There are $N - 1$ roads connecting the $N$ cities. The cost to destroy any given road is known. You are given the $K$ cities occupied by the enemy and the destruction cost of every road. Please compute the minimum total cost to isolate these $K$ enemy corps from each other, so that in the second step they can be eliminated one by one.

Input Format

• The first line contains two positive integers $N$ and $K$.
• The second line contains $K$ integers, indicating which cities are occupied by the enemy.
• The next $N - 1$ lines each contain three positive integers $a, b, c$, indicating there is a road between city $a$ and city $b$, and the cost to destroy it is $c$. City indices start from $0$.

Output Format

Output a single line with one integer, the minimum total cost.

5 3
1 2 4
1 0 4
1 3 8
2 1 1
2 4 3

4

Hint

Constraints:

• For $10\%$ of the testdata, $N \le 10$.
• For $100\%$ of the testdata, $2 \le N \le 10^5$, $2 \le K \le N$, $1 \le c \le 10^6$.

Translated by ChatGPT 5