Your state has just purchased a large, unspoiled tract of
land, and wishes to turn it into a nature park with hiking
trails. The land has $n$
places of interest to which guests may wish to hike, and of
these, $k$ are very
special. The state wishes to connect these places with hiking
trails. There are $m$
candidate hiking trails to choose from that directly connect
two places of interest with various costs. There are some
constraints for choosing the trails. First, there must be
exactly one way to hike from any place to any other place.
Second, exactly $w$ of the
trails must directly connect a special place with a regular
place. Of course, the state wishes to minimize the cost of
blazing these trails.
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs. The
first line of input will contain four integers $n$, $m$, $k$ and $w$, where $n$ ($2
\le n \le 2 \cdot 10^5$) is the number of places,
$m$ ($1 \le m \le 5 \cdot 10^5$) is the
number of potential direct trails between places, $k$ ($1
\le k < n$) is the number of special places, and
$w$ ($1 \le w \le n1$) is the number of
specialnonspecial direct trails the state wishes to blaze. The
places are numbered $1$ to
$n$.
Each of the next $k$
lines holds a single integer $s$ ($1
\le s \le n$) indicating the special places. These
values will be unique and will be in ascending order.
Each of the next $m$
lines will describe a potential trail that the state could
blaze. Each of these lines will consist of three integers,
$a$, $b$ and $c$, where the trail would go between
places $a$ and
$b$ ($1 \le a,b \le n, a \ne b$) and would
cost $c$ ($1 \le c \le 10^5$). No two places
will have more than one potential trail between them, and a
trail from $a$ to
$b$ is the same as a trail
from $b$ to $a$.
Output
Output a single integer, which is the minimum total cost for
the state to blaze trails in their new park subject to their
constraints, or $1$ if it
isnâ€™t possible.
Sample Input 1 
Sample Output 1 
3 3 1 2
2
1 2 2
1 3 1
2 3 3

5

Sample Input 2 
Sample Output 2 
3 1 1 1
2
1 2 2

1
