Baltic Olympiad in Informatics: 2016 Day 2, Problem 1

There are ~n~ cities in Byteland, and ~k~ of them are important cities frequently visited by the king of Byteland.

There are also ~m~ roads in the country, each of them connecting two cities. Unfortunately, the condition of the roads is so bad that the king cannot drive through them at full speed with his sports car.

For each road, the cost for renovating it is known. Your task is to choose which roads will be renovated so that all ~k~ important cities are connected with renovated roads, and the total cost is as low as possible.

Constraints

For all subtasks:

~1 \le c \le 10^9~

~n \ge k~

Subtask 1 [22%]

~2 \le k \le 5~

~n \le 20~

~1 \le m \le 40~

Subtask 2 [14%]

~2 \le k \le 3~

~n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

Subtask 3 [15%]

~2 \le k \le 4~

~n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

Subtask 4 [23%]

~k = 4~

~n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

Subtask 5 [26%]

~k = 5~

~n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

Input Specification

The first input line contains three integers ~n~, ~k~ and ~m~: the number of cities, the number of important cities and the number of roads. The cities are numbered ~1, 2, \dots, n~. The second input line contains ~k~ integers: the important cities.

Finally, the input contains ~m~ lines that describe the roads. Each line contains three integers ~a~, ~b~ and ~c~, meaning that there is a bidirectional road between cities ~a~ and ~b~, and the renovation cost for the road is ~c~.

You may assume that there is a route between any two cities.

Output Specification

You should output the minimum total cost for renovating the roads so that the king can travel between all important cities with his sports car.

Sample Input

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

Sample Output

11