Scofield is a hero in American show “Prison Break”. He had broken the prison and started a big runaway. Scofield has a map of US with cities and bidirectional roads between them. The lengths of roads are known. Some cities get a lot of cops who are very troublesome. Now Scofield needs your help to arrange his runaway route. He needs a shortest path between two cities, while the quantity of the police in any city, except the start city and end city, on the route is no more than k. You should know that it is very hard to escape. Scofield is very smart but not good at computer. Now Scofield is in trouble, can you help him with your computer?

The input consists of several test cases. There is an integer T on the first line indicating the number of test cases. For each case, the first line consists of two integers N and M. N is the number of cities; M is the number of roads. The next line contains N integers C1, C2... CN, where Ci is the number of cops in city i. Then followed M lines, each line consists of three integer, u, v, w, indicating there is a road with length w between city u and city v. The following line consists of an integer Q, indicating the number of queries. Each of the following Q lines consists of three integers, u, v, k, indicating the query for the shortest path between city u and city v with limitation of k cops. Technical Specification 1. T <= 20 2. 2 <= N <= 200, 0 <= M <= n * (n – 1) / 2 3. 0 <= Ci <= 1000,000,000 4. 0 <= u, v < N, 0 <= w <= 1000, 0 <= k <= 1000,000,000 5. 0 <= Q <= 100000 6. There is no more than ONE road between two cities and no road between the same cities. 7. For each query, u is not equal to v. 8. There is ONE empty line after each test case.

For each query, output a single line contains the length of the shortest path. Output “-1” if you can’t find the path. Please output an empty line after each test case.

The 4th Baidu Cup Central China Invitational Programming  Contest (Final Round)