Voting Cities

Time limit1sMemory limit1024 MB

Summary

For each start city and ticket prices, find the cheapest road path to a voting city, where each of five discount tickets can be used at most once.

Level: Hard8 of 10
Topics: Shortest path, Bit manipulation, Graph
Solved: No attempts yet

Problem

The great Emperor, Lord Pooty, has decided to retire and hand the crown to one of his many sons. In the spirit of democracy, he will settle the succession with a vote.

The kingdom has $N$ cities numbered from $0$ to $N - 1$ . Of these, $K$ are voting cities, and the $i$ th voting city is $T_i$ .

As a responsible citizen, you will travel to one of the designated voting cities to cast your vote. There are $E$ roads. Road $j$ goes from city $U_j$ to city $V_j$ in one direction and has toll $C_j$ . Local cities have opened a ticket system to reduce travel costs.

There are 5 ticket types, numbered 1 to 5. A ticket of type $x$ reduces the toll of a road by $(10x)\%$ , so the toll is multiplied by $\left(1 - \frac{x}{10}\right)$ when that ticket is used.

Ticket rules: you cannot use more than one ticket on a single road. You may buy at most one of each type at the start of your journey. For example, you may buy one type 1 ticket and one type 2 ticket, but not two type 2 tickets. This prevents hoarding. Tickets can only be bought at the start of the journey.

You are busy and do not know in advance which city you start from or the ticket prices. You have a list of $Q$ situations, each with a starting city $S$ and prices $P_1$ through $P_5$ for the five tickets. A ticket may be unavailable, in which case its price is $-1$ .

For each situation, find the minimum cost to reach a voting city, if one is reachable by road. Not every city can reach every other city, so you may have to walk.

Input

The first line has three integers $N$ , $E$ , and $K$ : the number of cities, roads, and voting cities. The second line has $K$ integers, where the $i$ th is $T_i$ , the $i$ th voting city.

Each of the next $E$ lines has three integers $U_j$ , $V_j$ , $C_j$ , describing a one-way road from $U_j$ to $V_j$ with toll $C_j$ .

The next line has $Q$ , the number of situations. Each of the next $Q$ lines has six integers $S$ , $P_1$ , $P_2$ , $P_3$ , $P_4$ , $P_5$ : the starting city and the prices of tickets 1 through 5.

The program reads from standard input.

Output

Print $Q$ lines, one integer per line. Each integer is the lowest cost to a voting city for the corresponding situation, in input order. Print $-1$ if no voting city is reachable from the starting city.

The program writes to standard output.

Constraints

$1 \le N \le 5000$
$0 \le E \le 10000$
$1 \le Q \le 100$
$0 \le K \le N$
$0 \le T_i < N$ for all $1 \le i \le K$
$T_i \ne T_j$ for all $1 \le i < j \le K$
$1 \le C_i \le 10^9$ for all $1 \le i \le E$
$C_i$ is a multiple of $10$ for all $1 \le i \le E$
$0 \le U_i, V_i < N$ and $U_i \ne V_i$ for all $1 \le i \le E$
$-1 \le P_i \le 10^9$ for all $1 \le i \le 5$

Examples3

Example 1

Input

3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1

Expected output

Example 2
Input
```
2 0 1
1
1
0 -1 -1 -1 -1 -1
```
Expected output
```
-1
```

Example 3

Input

6 3 2
4 5
0 4 100
1 4 200
2 5 300
4
0 -1 -1 -1 -1 -1
1 20 40 10 100 4
2 1 2 3 4 0
3 0 -1 0 0 0

Expected output