Minimum Round-Trip Delivery Time

A courier service needs to deliver a series of packages to various cities. The cities are connected by roads, and each road has a travel time associated with it. The company can carry only one package at a time; hence, each delivery requires a round trip from the starting city to the destination and back.

Your task is to compute the total minimum time required to deliver all the packages. The time taken to deliver a package is twice the shortest distance from the starting city to the destination city (since the courier must return to the starting point after each delivery). If a package is destined for the starting city, no travel is necessary for that package.

The road network is given as an undirected graph with N cities and R roads. Each road connects two cities and has an associated travel time. You are required to build the graph, compute the shortest path from the starting city to every other city using Dijkstra's algorithm, and then sum up the round-trip times to all package destinations.

Formally, if the shortest distance from the starting city s to a destination city p is \(d(s, p)\), then the delivery time for that package is \(2 \times d(s, p)\) (if \(p \neq s\)). The answer is the sum of the delivery times for all packages.

inputFormat

The input is read from the standard input (stdin) and has the following format:

N
R
u1 v1 t1
u2 v2 t2
... 
uR vR tR
s
P
p1 p2 ... pP

Where:

• N is the number of cities (indexed from 0 to N-1).
• R is the number of roads.
• Each of the next R lines contains three integers: u and v (the cities connected by the road) and t (the travel time of that road). The roads are undirected.
• s is the starting city index.
• P is the number of packages to be delivered.
• The next line contains P integers representing the destination cities for the packages. (If P is 0, this line will be empty.)

outputFormat

The output is a single integer printed to the standard output (stdout) representing the total minimum time required to deliver all the packages.

## sample

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

10