#2466. 加满油箱

加满油箱

Description

城市之间的油价是不一样的,编写程 序,寻找最便宜的城市间旅行方式。在旅行途中可以加满油箱。假设汽 车每单位距离使用一单位燃料,从一个空油箱开始。

Format

Input

输入的第11行包含n1n1000n (1≤n ≤1000)m0m10000m (0≤m ≤10000),表示城市和道路的数量。下一行包含nn 个整数pi1pi100p_i (1≤p_i≤100),其中pip_i 表示第ii 个城市的燃油价格。接下来的mm 行,每行都 包含33个整数uv0u,v<nu 、v (0≤u , v <n )d1d100d (1≤d ≤100),表示在uuvv 之间有一条路,长度为dd 。接下来一行是查询数q1q100q (1≤q≤100)。再接下来的qq 行,每行都包含33个整数c1c100c (1≤c ≤100)ssee ,其中cc 是车辆的油箱容量,ss 是起点城市,ee 是终点城市。

Output

对于每个查询,都输出给定容量的汽车从ssee 的最便宜 旅程的价格,如果无法从ssee ,则输出“impossible”。

Samples

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
170
impossible

来源

POJ3635