Description

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

Format

Input

输入的第$1$行包含$n （1≤n ≤1000）$和$m （0≤m ≤10000）$，表示城市和道路的数量。下一行包含$n$个整数$p_i （1≤p_i≤100）$，其中$p_i$ 表示第$i$个城市的燃油价格。接下来的$m$ 行，每行都 包含$3$个整数$u 、v （0≤u , v <n ）$和$d （1≤d ≤100）$，表示在$u$ 和$v$ 之间有一条路，长度为$d$ 。接下来一行是查询数$q （1≤q≤100）$。再接下来的$q$ 行，每行都包含$3$个整数$c （1≤c ≤100）$、$s$ 和$e$ ，其中$c$ 是车辆的油箱容量，$s$ 是起点城市，$e$是终点城市。

Output

对于每个查询，都输出给定容量的汽车从$s$ 到$e$的最便宜 旅程的价格，如果无法从$s$ 到$e$ ，则输出“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