# A Monster for Gallina's owner P47592

Statement

thehtml

Marc is leaving his flat to go to the university. He has been working hard for the last couple of days to fool everyone into believing that he has made some progress on his PhD thesis. Furthermore, he had to find food for Gallina, his Minecraft parrot. Since he feels really tired, he urgently needs to buy a Monster energy drink (and also because he is severely addicted).

Marc decides to buy it on his way to the university. How many seconds will it take him to get there, if he does so optimally? We model the city as a weighted undirected graph with n vertices (from 0 to n−1) and m edges. Marc’s flat is at vertex 0, and the university is at vertex n − 1. There are k ‍supermarkets. Marc will spend exactly one minute inside a supermarket to buy his drink.

Input

Input consists of several cases, each with n, m and k, followed by m triples x y c for an edge between x and y (with xy) that takes c seconds to transverse (an integer). Follow the k ‍positions of the supermarkets, all different and between 1 and n − 2. Assume 3 ≤ n ≤ 104, 2 ≤ m ≤ 5n, 1 ≤ kn − 2, that there is at most one edge between every pair of vertices, and 1 ≤ c ≤ 105.

Output

For each case, print the minimum time to reach the university buying a Monster drink, if it is possible. Otherwise, print “impossible”.

Public test cases
• Input

```3 3 1
1 0 10  2 1 10  0 2 15
1

8 8 2
0 3 15  4 5 10  0 2 20  2 6 5
4 7 40  3 5 30  4 1 25  1 2 5
6 5

4 2 2
0 1 100  2 3 100
1 2

3 2 1
2 0 100000  0 1 100000
1
```

Output

```80
155
impossible
300060
```
• Information
Author
Víctor Martín and Marc Felipe
Language
English
Official solutions
C++
User solutions
C++