Landline Telephone Network#7531
The mayor of RMR city wants to create a secure telephone network that can be used in emergency situations when the city becomes cut off from the outside world. Some pairs of buildings in the city can be directly connected by a telephone line. The city engineers have prepared cost estimates for connecting each such pair.
The mayor needs your help: it is necessary to build the cheapest possible network that connects all buildings in the city while satisfying the safety requirements described below. A call from building to building must be made along a simple path (that is, a path that does not contain any repeated buildings). Among all the buildings, there are several unsafe ones, inhabited by people with a criminal background. The mayor wants these buildings to have only access to the network, but not to serve as transit nodes. In other words, no connection between buildings and should pass through an unsafe building (where is different from both and ).
The first line contains three integers n, m, p, where n~(1 \le n \le 1000) is the number of buildings, m~(0 \le m \le 10^5) is the number of possible direct connections between pairs of buildings, and p~(0 \le p \le n) is the number of unsafe buildings. The buildings are numbered from to .
The second line contains distinct integers from to inclusive — the numbers of unsafe buildings.
Each of the following lines contains three integers x_i, y_i, and l_i, describing one potential direct connection: x_i and y_i~(1 \le x_i, y_i \le n) are distinct building numbers connected by the line, and l_i~(1 \le l_i \le 10000) is the cost of this connection.
There is at most one direct connection between any pair of buildings.
Print the cost of the cheapest network that satisfies the safety conditions, if possible. Otherwise, print "impossible".
Example 1
Example 2