Cargo Trains

The International Cargo and Packaging Company Inc. (ICPC Inc.) transports cargo between two cities: Source City and Sink City. ICPC Inc. does not have its own fleet, instead it contracts the service of two train companies, the company A and company B. Each company has its own network that connects some of the cities at prices that the company decides. For two given cities, it is possible that the route between them is served by both companies, only one company, or none. ICPC Inc. has reached an agreement with both companies that allows it to use their combined services at a discount price, but it has to follow these rules:

1. For a given shipment, ICPC Inc. must specify the percentage of participation of each company given by a for company A and (1 − a) for company B, for a given real number a (0 ≤ a ≤ 1).
2. When the segment between two cities is served by only one company, ICPC Inc. will pay the price corresponding to that company.
3. When the segment between two cities is served by both companies, the shipment can be shipped using a train from any of the two companies and will pay a fare equal to a×CA +(1−a)×CB, where CA and CB correspond to the fares of company A and B respectively.
4. A shipment could pass through several intermediate cities. The total cost of the shipment corre- sponds to the sum of the costs of the individual segments between cities calculated according to rules 2 and 3. ICPC Inc. needs your help to optimize its costs. Specificaly, ICPC Inc. needs to evaluate the cost of different alternatives that combine the participation of the two train companies in different proportions. Given the networks and prices of companies A and B, your task is to calculate the cost of k different combination alternatives. Each alternative is specified by the participation of company A, which corresponds to a real number 0 ≤ a ≤ 1. Input The input contains multiple test cases. Each test case starts with a line with four integer values separated by spaces, n, ma, mb and k, that correspond to the number of cities, the number of edges in the network of company A, the number of edges in the network of company B, and the number of combination alternatives respectively. The ranges for the values are: 2 ≤ n ≤ 100, 1 ≤ ma, mb ≤ 5000, and 1 ≤ k ≤ 10000. The next ma lines specify the network of company A. Each line has three integer values: Ni, Nj and Ci,j, separated by spaces, with 0 ≤ Ni,Nj < n and 0 ≤ Ci,j ≤ 1000000. The network is an undirected graph and each edge is only listed once. Ci,j corresponds to the cost of sending one kilogram of cargo from city Ni to city Nj or the other way around. Source City corresponds to 0 and Sink City to n − 1. Then next mb lines represent the graph corresponding to the network of company B represented in the same way as the network of company A. The last k lines of the test case contain the different combinations to be evaluated, one combination per line. A combination is represented by a real number, 0 ≤ a ≤ 1, with maximum 4 decimal digits. The value a specifies company A’s participation. Company B’s participation is implicitely defined and corresponds to 1 − a. You can suppose that there is at least one path between the Source City and the Sink City using routes served by any company. The end of the input is indicated by the line -1 -1 -1 -1.

2/2 Output For each combination alternative in each test case, the optimal cost of a trip from a city 0 to city n − 1 must be printed. If the answer has a decimal part, it has to be truncated without approximation. Sample input 3223 0 1 100 1 2 200 0 1 200 1 2 150 0 1 0.5 -1 -1 -1 -1 Sample Output 350 300 325