L. Drone Route Planning
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are in charge of an autonomous delivery drone navigating a futuristic smart city.

The city is represented as a directed weighted graph. Each hub is a node, and each aerial flight path is a one-way connection with a given energy cost.

Some hubs contain delivery packages.

The drone starts at hub $$$U$$$, and its mission is to:

  1. Take off from hub $$$U$$$.
  2. Collect exactly five packages.
  3. Return to hub $$$U$$$.
  4. Minimize the total energy cost.

The drone may revisit hubs and reuse flight paths multiple times.

If the drone visits a hub that contains a package, it is not required to collect it.

There are at most $$$35$$$ hubs in the city that contain packages.

Your task is to determine the minimum total energy cost required to complete the route:

Start at $$$U$$$ $$$\rightarrow$$$ collect 5 packages $$$\rightarrow$$$ return to $$$U$$$.

If no such route exists, output $$$-1$$$.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le M \le 10^5$$$) — the number of hubs and the number of directed flight paths .

The second line contains a single integer $$$U$$$ ($$$1 \le U \le N$$$) — the starting hub.

Each of the next $$$M$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b \le N$$$, $$$1 \le c \le 10^9$$$) — representing a directed flight path from hub $$$a$$$ to hub $$$b$$$ with energy cost $$$c$$$.

The next line contains a single integer $$$K$$$ ($$$0 \le K \le \min(N, 35)$$$) — the number of hubs that contain packages.

The next line contains $$$K$$$ distinct integers $$$v_1, v_2, \dots, v_K$$$ ($$$1 \le v_i \le N$$$) —the indices of the hubs that contain packages.

It is guaranteed that all $$$v$$$ are distinct.

Output

Print a single integer — the minimum total energy cost required for the drone to:

  • start at hub $$$U$$$,
  • collect exactly five packages,
  • and return to hub $$$U$$$.

If it is impossible to complete such a route, print $$$-1$$$.

Example
Input
8 12
1
8 1 2
1 3 2
3 2 1
2 6 12
3 6 8
6 5 2
3 5 5
5 7 4
7 1 6
7 8 10
7 4 3
4 8 9
6
2 3 4 5 6 7
Output
27