Server Time: Sun Sep 20, 2020 10:38 pm
 Welcome ( logout )
G - A Wedding Party
 PDF (English) Ranklist
 Time Limit: 3 second(s) Memory Limit: 32 MB

Now given the location of the shops you have to find the route from junction 0 to junction N-1 which will visit maximum number of shops with minimum time (first maximize the number of shops then minimize the time to visit them). We can visit a junction more than once.

# Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case begins with three non negative integers N (2 ≤ N ≤ 500), M (1 ≤ M ≤ 10000) S (0 ≤ S ≤ 15). Next line contains S integers denoting the shop locations. Each of the next M lines contains three integers u, v, w (0 < u, v < N, u ≠ v, 1 ≤ w ≤ 100) denoting a road from u to v with cost w.

# Output

For each case of input you have to print the case number and two integers representing maximum number of shops we can visit in the way and the minimum time required to reach junction N-1 after visiting maximum number of shops. If we cannot attend the contest, print "Impossible". See samples for more details.

# Output for Sample Input

2

4 4 4

0 1 2 3

0 1 10

1 3 30

0 2 30

2 3 5

4 4 4

0 1 2 3

0 1 10

3 1 30

0 2 30

3 2 5

Case 1: 3 35

Case 2: Impossible