题目描述

有$\red{N}$个城市（编号$\red{0、1…N-1}$）和$\red{M}$条道路，构成一张无向图。

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

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

输入格式

第一行包含两个整数$\red{N}$和$\red{M}$。

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

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

接下来一行包含一个整数$\red{q}$，代表问题数量。

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

输出格式

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

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

每个结果占一行。

样例

输入样例

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

提示

$\red{1≤N≤1000}$,

$\red{1≤M≤10000}$,

$\red{1≤p_i≤100}$,

$\red{1≤d≤100}$,

$\red{1≤C≤100}$

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