A Monster for Gallina's owner P47592


Statement
 

pdf   zip

html

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 x ≠ y) 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 ≤ k ≤ n − 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++