176. 装满的油箱

有 $N$ 个城市(编号 $0、1…N-1$)和 $M$ 条道路,构成一张无向图。

在每个城市里边都有一个加油站,不同的加油站的单位油价不一样。

现在你需要回答不超过 $100$ 个问题,在每个问题中,请计算出一架油箱容量为 $C$ 的车子,从起点城市 $S$ 开到终点城市 $E$ 至少要花多少油钱?

注意: 假定车子初始时油箱是空的。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数,代表 $N$ 个城市的单位油价,第 $i$ 个数即为第 $i$ 个城市的油价 $p_i$。

接下来 $M$ 行,每行包括三个整数 $u,v,d$,表示城市 $u$ 与城市 $v$ 之间存在道路,且车子从 $u$ 到 $v$ 需要消耗的油量为 $d$。

接下来一行包含一个整数 $q$,代表问题数量。

接下来 $q$ 行,每行包含三个整数 $C、S、E$,分别表示车子油箱容量 $C$、起点城市 $S$、终点城市 $E$。

输出格式

对于每个问题,输出一个整数,表示所需的最少油钱。

如果无法从起点城市开到终点城市,则输出 impossible

每个结果占一行。

数据范围

$1 \le N \le 1000$,
$1 \le M \le 10000$,
$1 \le p_i \le 100$,
$1 \le d \le 100$,
$1 \le C \le 100$

输入样例:

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