Minimum Steiner Tree

Given an undirected connected graph \(G=(V,E)\) with \(n\) nodes and \(m\) weighted edges, and a set \(S\) consisting of \(k\) nodes, select a subgraph \(G'=(V',E')\) such that:

• \(S \subseteq V'\).
• \(G'\) is connected.
• The sum of the weights of the edges in \(E'\) is minimized.

Your task is to output the sum of the weights of the edges in the optimal subgraph \(G'\).

This problem is equivalent to the Steiner Tree problem. Note that in general the Steiner Tree problem is NP-hard. However, the constraints in the contest are assumed to be small enough to allow a solution using state space dynamic programming (bitmask DP) and shortest path relaxation.

Formally, if you define a DP state \(dp[mask][v]\) as the minimum cost to connect the set of terminals indicated by \(mask\) ending at vertex \(v\), then the recurrence can be given as:

$$dp[mask][v] = \min_{mask_1 \cup mask_2 = mask \; \text{and} \; mask_1 \cap mask_2 = \emptyset} \Bigl(dp[mask_1][v] + dp[mask_2][v]\Bigr) $$

Followed by a relaxation over the edges of the graph:

$$dp[mask][u] = \min(dp[mask][u], dp[mask][v] + w(v,u)) $$

The answer is (\min_{v \in V} dp[2^k - 1][v]).

</p>

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of nodes and the number of edges in the graph.

The following \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

The next line contains a single integer \(k\), the number of nodes in the set \(S\).

The last line contains \(k\) distinct integers representing the nodes in \(S\>.

outputFormat

Output a single integer denoting the minimum sum of the weights of the edges in the required subgraph.

sample

4 3
1 2 1
2 3 2
3 4 3
2
1 4

6