In recent years, electric vehicles are highly promoted to reduce emissions of greenhouse gas. However, the limited battery capacity of electric vehicles requires visits of recharging stations during the vehicles' tours. In this problem, you are going to plan a route for an electric vehicle to travel from an origin to a destination with the least total cost to charge electricity.

Consider an undirected graph with `n` nodes and `m` arcs, denoted by 1, 2, ..., `n`, where each node represents a location, and each edge (`i`, `j`) represent a two-way road connecting location `i` and location `j`. There are `h` recharging stations located at nodes `s _{1}`,

Figure 2. An illustrated example with all `d _{ij}` equal to 1, where the best routing of the car is to visit node 1, node 2, node 8 (charging electricity of 3 kWh), node 2, node 3, node 4, and node 5, achieving the minimal total charging cost of 3 dollars.

First line of the input is an integer `T` indicating the number of test cases. For each case, the first line contains six integers `n`, `m`, `h`, `a`, `b`, `Q`, and `L`, where 1 ≤ `h`, `a`, `b` ≤ `n` ≤ 1000, 1 ≤ `m` ≤ 10000, 0 ≤ `L` ≤ `Q` ≤ 1000000. The second line contains `h` integers representing locations of recharging stations `s _{1}`,

For each case, if the car cannot arrive at the destination `b`, then output -1, otherwise, output an integer that equals the minimum total charging cost of electricity for the car to travel from origin `a` to destination `b`.

提交代码