Problem Description

You are given an undirected connected graph $G=(V,E)$ with $n$ vertices and $m$ weighted edges.

You are also given a set $S$ containing $k$ vertices. Choose a subgraph $G'=(V',E')$ of $G$ such that:

1. $S\subseteq V'$.
2. $G'$ is connected.
3. The sum of edge weights in $E'$ is minimized.

You only need to output the sum of edge weights in $E'$.

Input Format

The first line contains three integers $n,m,k$, representing the number of vertices, the number of edges in $G$, and the size of $S$.

The next $m$ lines each contain three integers $u,v,w$, indicating an undirected edge between vertices $u$ and $v$ with weight $w$.

The next line contains $k$ distinct positive integers, representing the elements of $S$.

Output Format

The first line contains one integer, the minimum possible sum of edge weights in $E'$.

7 7 4
1 2 3
2 3 2
4 3 9
2 6 2
4 5 3
6 5 2
7 6 4
2 4 7 5

11

Hint

[Sample Explanation]

The graph in the sample is shown in the figure below. The red vertices are the elements in $S$, and the red edges are the elements in $E'$. In this case, the sum of all edge weights in $E'$ is $2+2+3+4=11$, which is the minimum.

[Constraints]

For $100\%$ of the testdata, $1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6$.

The given undirected graph is guaranteed to be connected, but there may be multiple edges and self-loops.

Translated by ChatGPT 5