Hide

# Problem DPedal Power Photo courtesy of Christy Coghlan Figure 1: This figure shows sample input $1$, with bike paths in red/curved and non-bike paths in black/straight.

## Input

The problem input describes a multigraph with two different types of edges: edges for bike paths and edges for non-bike paths.

The first line contains one integer $n$, $0 < n \leq 300$, the number of locations on campus. The locations are numbered from $0$ to $n-1$. Location $0$ is your home, which is the starting and ending location of you and your bike.

The second line contains one integer $x$, $0 < x \leq n(n-1)/2$, the number of bike paths.

Each of the next $x$ lines contains a description of a bike path. Each line has $3$ integers $u$ $v$ $t$, where $0 \leq u < n$ is the starting location of the path, $0 \leq v < n$ is the ending location of the path, and $0 \leq t \leq 10^6$ is the time it takes to travel from $u$ to $v$ and from $v$ to $u$ by bike.

The next line contains one integer $y$, $0 < y \leq n(n-1)/2$, the number of non-bike paths.

Each of the next $y$ lines contains a description of a non-bike path. Each line has $3$ integers $u$ $v$ $t$, where $0 \leq u < n$ is the index of the starting location of the path, $0 \leq v < n$ is the index of the ending location of the path, and $t \leq 10^6$ is the time it takes to travel from $u$ to $v$ and from $v$ to $u$ using a bike alternative.

All paths can be taken in either direction, and the amount of time it takes to travel in either direction of the same path is the same. There are at most one bike path and at most one non-bike path between any two locations. No path starts and ends at the same location.

The next line contains an integer $z$, $0 < z \leq 300$, indicating the number of locations you have to visit on your route. The next line contains $z$ integers $0 \leq a_1, a_2, \ldots , a_ z < n$, the indices of the locations you must visit. The locations must be visited in the order in which they are listed, but there are no restrictions on how often you may pass through any location on your trip.

## Output

Output the minimum possible cumulative travel time, with you and the bike starting and ending at location $0$. You are guaranteed that all locations on your route can be reached using some combination of bike and non-bike paths.

Sample Input 1 Sample Output 1
4
4
0 1 2
3 1 10
2 3 2
2 0 10
4
1 0 11
3 1 3
2 3 11
2 0 3
3
1 3 2

16