Minimum Supply Points on Shortest Paths

T country has N cities (numbered 1 to N) connected by M bidirectional roads. Each road has a positive length. There are K distressed cities. The government will send a rescue team from the capital (city 1) to each distressed city along one of the shortest paths. In addition, only some cities are allowed to have supply points (this property is independent of whether a city is the capital or a distressed city). To speed up rescue operations, the government wants to build as few supply points as possible among the allowed cities so that for each distressed city there exists at least one shortest path from city 1 to that city that passes through at least one supply point.

Given the information of the cities and roads, determine the minimum number of supply points that need to be established. If it is impossible to cover every distressed city under the restrictions, output -1.

The shortest path condition is formally defined as follows. Let \(d(i)\) be the shortest distance from city 1 to city \(i\). For an undirected road connecting \(u\) and \(v\) with length \(w\), if \(d(u)+w=d(v)\) then we say that the directed edge \(u\to v\) is part of a shortest path. A city \(u\) is said to lie on a shortest path from 1 to \(v\) if there is a sequence of directed edges in the shortest‐path DAG (constructed by all directed edges \(u\to v\) satisfying \(d(u)+w=d(v)\)) from 1 to \(v\) that goes through \(u\).

You are also given the list of cities where a supply point can be built. Note that even if a city is the capital or distressed, if it is allowed then a supply point can be built there. Building a supply point in a city is equivalent to “covering” that vertex. Your task is to choose a minimum subset of allowed cities such that for every distressed city, there exists at least one shortest path from 1 to that city which includes at least one of the chosen supply cities.

Hint: This problem can be reduced to finding a minimum vertex cut in the shortest-path DAG, where only allowed cities can be chosen (with a cost of 1 per allowed city) and all other cities have an infinite removal cost. Use a standard vertex splitting technique to transform the vertex cut problem into an edge cut problem and solve it using a max flow algorithm.

inputFormat

The input begins with two integers N and M (number of cities and roads). The next M lines each contain three integers u, v, and w describing a bidirectional road between cities u and v with length w (\(w>0\)).

The next line contains an integer K denoting the number of distressed cities, followed by a line with K distinct integers representing the distressed cities.

The next line contains an integer P denoting the number of cities which are allowed to have a supply point, followed by a line with P distinct integers representing the allowed cities. (If P is 0, then no city is allowed to have a supply point.)

outputFormat

Output a single integer: the minimum number of supply points needed. If it is impossible to cover every distressed city, output -1.

sample

2 1
1 2 5
1
2
1
2

1