задача
There are nn cities in Byteland, and kk of them are important cities frequently visited by the king of Byteland.
There are also mm 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 kk important cities are connected with renovated roads, and the total cost is as low as possible.
Input
The first input line contains three integers nn, kk and mm: the number of cities, the number of important cities and the number of roads. The cities are numbered 1,2,…,n1,2,…,n. The second input line contains kk integers: the important cities.
Finally, the input contains mm lines that describe the roads. Each line contains three integers aa, bb and cc, meaning that there is a bidirectional road between cities aa and bb, and the renovation cost for the road is cc.
You may assume that there is a route between any two cities.
Output
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.
Example
Input:
4 3 61 3 41 2 41 3 91 4 62 3 22 4 53 4 8
Output:
11
Subtasks
In all subtasks 1≤c≤1091≤c≤109 and n≥kn≥k.
Subtask 1 (22 points)
-
2≤k≤52≤k≤5
-
n≤20n≤20
-
1≤m≤401≤m≤40
Subtask 2 (14 points)
-
2≤k≤32≤k≤3
-
n≤105n≤105
-
1≤m≤2⋅1051≤m≤2⋅105
Subtask 3 (15 points)
-
2≤k≤42≤k≤4
-
n≤1000n≤1000
-
1≤m≤20001≤m≤2000
Subtask 4 (23 points)
-
k=4k=4
-
n≤105n≤105
-
1≤m≤2⋅1051≤m≤2⋅105
Subtask 5 (26 points)
-
k=5k=5
-
n≤105n≤105
-
1≤m≤2⋅1051≤m≤2⋅105
