Election Road Toll Optimization

Your country’s President, \(\mathbf{Lord\ Pooty}\), is about to retire. To decide his successor among his sons, he has arranged a voting process. There are \(N\) cities (numbered from \(0\) to \(N-1\)) in the country, but only \(K\) of them are designated as voting cities. Their indices are given by \(T_i\) (\(0 \le i < K\)).

You want to fulfill your duty as a citizen and vote. However, you do not know from which city you will start. Moreover, the tolls on the roads require careful planning. There are \(E\) directed roads; the \(j\)th road goes from city \(U_j\) to city \(V_j\) with a toll cost \(C_j\). To ease the journey, the country offers 5 types of discount coupons. When you use the \(x^{th}\) coupon on a road with toll \(y\), you only need to pay \(y \times (10x)\%\), i.e. the cost becomes \(y\times\frac{x}{10}\). Each coupon (from \(x=1\) to \(5\)) can be bought at most once.

You are given \(Q\) queries. In each query, you are given a starting city \(S\) and the purchase prices \(P_1, P_2, P_3, P_4, P_5\) for the coupons. Note that if a coupon is not available for purchase, its price is given as \(-1\). When you use a coupon, you must pay its purchase price (if available and if you haven’t used it before) and then, for that road, you pay the discounted toll cost as explained above. You cannot use one coupon more than once, and you may choose to traverse a road without using any coupon (paying the full toll \(y\)).

Your task is to determine, for each query, the minimum total cost needed to travel from the starting city \(S\) to any voting city. If no voting city is reachable, output \(-1\).

Note: The discount when using coupon \(x\) converts a toll \(y\) into a cost of \(y \times \frac{x}{10}\). All formulas are given in \(\LaTeX\) format when applicable.

inputFormat

The input begins with a line containing three integers \(N\), \(K\), and \(E\) representing the number of cities, the number of voting cities, and the number of roads respectively.

The next line contains \(K\) distinct integers \(T_0, T_1, \ldots, T_{K-1}\) representing the indices of the voting cities.

Then \(E\) lines follow, each containing three integers \(U_j\), \(V_j\), and \(C_j\) indicating there is a directed road from city \(U_j\) to city \(V_j\) with toll cost \(C_j\).

Next, an integer \(Q\) is given indicating the number of queries. Each of the following \(Q\) lines contains 6 integers: the starting city \(S\) followed by the coupon prices \(P_1, P_2, P_3, P_4, P_5\). A coupon price of \(-1\) indicates that the corresponding coupon is not available for that query.

outputFormat

For each query, output on a separate line a single number: the minimum cost required to reach any voting city from the starting city \(S\). If no voting city is reachable, output \(-1\).

sample

5 1 6
4
0 1 100
1 2 100
2 4 100
0 3 50
3 4 200
1 4 500
3
0 10 20 30 40 50
2 10 10 10 10 10
4 -1 -1 -1 -1 -1

200
20
0