Voting Cities

문제

The great Emperor, Lord Pooty, decided to retire and would like to hand over the crown to one of his many sons. In the spirit of democracy, he decided to do this with a vote! His kingdom consists of $NN$ cities labelled from $00$ to $N-1N\; -\; 1$. Of these $NN$ cities, $KK$ of them are voting cities where voting can be done. The $ii$th voting city is $T_{i}T\_i$.

As a reponsible member of society, you decided that it is only right for you to do your civic duty. You are to travel to one of the designated voting cities to vote! There are $EE$ roads that can be used. Road $jj$ connects city $U_{j}U\_j$ to city $V_{j}V\_j$ in one direction and has a toll of $C_{j}C\_j$. Luckily, due to this event, local cities have opened a ticket system to reduce the cost of traveling.

There are $55$ different types of tickets to choose from, numbered from type $11$ to type $55$. A ticket of type $xx$ will reduce the cost of the toll on a road by $(10x)\mathrm{\%}(10x)\backslash \%$. In other words, the cost of the road will be multiplied by $(1-\frac{x}{10})\backslash left(1\; -\; \backslash frac\{x\}\{10\}\backslash right)$ if a ticket of type $xx$ is used.

However, there are a few rules regarding the tickets. You cannot use more than one ticket on one road to stack the effects. You are only allowed to buy at most one of each ticket at the start of your journey. For example, you can choose to buy one type $11$ ticket and one type $22$ ticket but are not allowed to buy two type $22$ tickets. This is to prevent people from hoarding the tickets. You are only allowed to buy the tickets at the start of your journey.

You are a busy man and unfortunately, you do not know which city you may start your journey from, nor do you know the ticket prices. You have made a list of $QQ$ possible situations, comprised of a starting city $SS$ and ticket prices $P_{1}P\_1$, $P_{2}P\_2$, $P_{3}P\_3$, $P_{4}P\_4$ and $P_{5}P\_5$ for the $55$ tickets. It is possible that a certain ticket may not even be available, and in that case the ticket price will be $-1-1$.

For each of these situations, find the minimum cost to one of the voting city if it is reachable by road. Do note that not every city is reachable from every other and you may have to walk..

입력

Your program must read from standard input.

The first line of input contains $33$ integers $NN$, $EE$ and $KK$ representing the number of cities, number of roads and number of voting cities respectively. The second line contains $KK$ integers, the $ii$th one representing $T_{i}T\_i$, the $ii$th voting city.

The next $EE$ contain $33$ integers each. The $jj$th of these lines consists of $U_{j}U\_j$, $V_{j}V\_j$ and $C_{j}C\_j$ respectively, representing a unidirectional road from $U_{j}U\_j$ to $V_{j}V\_j$ with cost $C_{j}C\_j$. It is guaranteed that $C_{j}C\_j$ is divisible by $1010$.

The next line contains a single integer $QQ$, representing the number of situations to be considered.

The next $QQ$ lines contain $66$ integers $SS$, $P_{1}P\_1$, $P_{2}P\_2$, $P_{3}P\_3$, $P_{4}P\_4$ and $P_{5}P\_5$ representing the starting city and the prices of the tickets of type $11$ to type $55$ respectively. Note that the starting city and ticket prices can differ across the different situations provided.

출력

Your program must print to standard output.

Output $QQ$ lines with $11$ integer on each line, representing the lowest cost to a voting city for each situation in the order provided in the input. If a path does not exist for a situation, print $-1-1$ instead.

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

280

2 0 1
1
1
0 -1 -1 -1 -1 -1

-1

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

100
104
150
-1