Like no Tomorrow

I know it will be difficult. The test is demanding, and we are still a ragtag band. But that changes nothing. The semla awaits, and the test must be taken...

Hello, Sensei. It's Airi. The After-School Sweets Club has finished our final band practice at school, and we're about to head to the concert venue. But getting there has become a little complicated...

We need to take buses from school to the venue. There are regular buses and loop buses, and their fares work differently. And since we're the After-School Sweets Club, stopping at a dessert cafe before the show is a must, right? But we don't have much money, so we need to find the cheapest way to get to the venue.

Natsu is the best at explaining things, so I asked her to explain the rest.

In a directed graph $G$ with $N$ vertices and $M$ weighted edges, the After-School Sweets Club must travel from the school at vertex $1$ to the concert venue at vertex $N$. They must visit at least one dessert cafe before reaching the venue, while minimizing the total cost of the journey. There is always a way to reach the venue from the school.

Among the vertices other than the school at vertex $1$ and the venue at vertex $N$, $K$ are dessert cafes. The club may take regular buses and loop buses any number of times. However, once they visit the venue by bus, they do not travel anywhere else. The two types of buses work as follows.

• Regular bus

  • When traveling between two different locations, the fare equals the distance traveled.
  • The distance traveled is the sum of the weights of the edges traversed.

• Loop bus

  • These buses operate only between mutually reachable vertices. Two vertices $u, v$ are mutually reachable if there is both a directed path from $u$ to $v$ and a directed path from $v$ to $u$.
  • The fare for a loop bus is the weight of the first edge taken from the vertex where the bus is boarded.

...That's what Natsu told me to write.

Sensei, please find the minimum cost for us to reach the concert venue.

The second line contains the vertex numbers of the dessert cafes, separated by spaces. These vertex numbers are between $2$ and $N - 1$, inclusive.

The next $M$ lines, starting from the third line, describe the edges. The $i$-th of these lines contains $u_i$, $v_i$, $c_i$, separated by spaces, representing a directed edge from vertex $u_i$ to vertex $v_i$ with weight $c_i$. $(1 \le u, v \le N$; $u \neq v$; $1 \le c_i \le 1\,000)$ For any two distinct edges $i, j$, $(u_i, v_i) \neq (u_j, v_j)$.

Time limit

2000 ms

Memory limit

1024 MB

Checker

CUSTOM