Michael Scofield has just broken out of the prison. He now wants to go to a certain city for his next unfinished job. As you are the only programmer in his gang, he asked for your help.

As you know that the fuel prices vary in the cities, you have to write a code to help Scofield that instructs him where to take the fuel and which path to choose. Assume that his car uses one unit of fuel in one unit of distance. Now he gives you the starting city s where he starts his journey with his car, the destination city t and the capacity of the fuel tank of his car c, the code should find the route that uses the cheapest fuel cost. You can assume that Scofield's car starts with an empty fuel tank.

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

Each case starts with a line containing two integers n (2 ≤ n ≤ 100) and m (0 ≤ m ≤ 1000) where n denotes the number of cities and m denotes the number of roads. The next line contains n space separated integers, each lies between 1 and 100. The i^th integer in this line denotes the fuel price (per unit) in the i^th city. Each of the next m lines contains three integers u v w (0 ≤ u, v < n, 1 ≤ w ≤ 100, u ≠ v) denoting that there is a road between city u and v whose length is w.

The next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries by Scofield. Each of the next q lines contains the request. Each request contains three integers: c s t (1 ≤ c ≤ 100, 0 ≤ s, t < n) where c denotes the capacity of the tank, s denotes the starting city and t denotes the destination city.

For each case, print the case number first. Then for each query print the cheapest trip from s to t using the car with the given capacity c or impossible if there is no way of getting from s to t with the given car.