题目描述

有 $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。

每个结果占一行。

样例

输入样例：

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

样例解释

城市油价：

• 城市0: 10
• 城市1: 10
• 城市2: 20
• 城市3: 12
• 城市4: 13

道路：

• (0,1) 距离 9
• (0,2) 距离 8
• (1,2) 距离 1
• (1,3) 距离 11
• (2,3) 距离 7

问题1：油箱容量 $C=10$，起点 $S=0$，终点 $E=3$
路径 $0 \to 2 \to 3$：
从 0 到 2 距离 8，在 0 加油至少 8 升，油价 10，费用 80
从 2 到 3 距离 7，油箱剩下 0 升，在 2 加油至少 7 升，油价 20，费用 140
总费用 220，不是最优。

更好的路径 $0 \to 1 \to 2 \to 3$：
0→1 距离 9，在 0 加 9 升，费用 90
1→2 距离 1，油箱剩 0 升，在 1 加 1 升，费用 10
2→3 距离 7，油箱剩 0 升，在 2 加 7 升，费用 140
总费用 240，也不是最优。

实际上最优路径 $0 \to 2 \to 3$ 但加油策略不同：
在 0 加满 10 升（因为容量 10），费用 100
开到 2 消耗 8 升，剩 2 升
在 2 加 6 升（补到刚好够到 3），油价 20，费用 120
总费用 220，还是不好。

更优：$0 \to 1 \to 2 \to 3$：
在 0 加 9 升到 1，费用 90
在 1 加 1 升到 2，费用 10
在 2 加 7 升到 3，费用 140
总 240，更差。

可能最优是 $0 \to 2 \to 3$：
在 0 加 10 升，费用 100
到 2 剩 2 升
在 2 加 8 升（因为从 2 到 3 要 7 升，剩 1 升），费用 160
总 260？不对。

实际上样例输出是 170，说明有更优方案：
$0 \to 2 \to 3$：
在 0 加 8 升到 2，费用 80
在 2 加 7 升到 3，费用 140
总 220，不符。

或者 $0 \to 1 \to 2 \to 3$：
在 0 加 9 升到 1，费用 90
在 1 加 8 升（到 2 用 1 升，剩 7 升刚好到 3），费用 80
总 170，符合！

问题2：$C=20, S=1, E=4$
城市 4 与其他城市没有道路相连，所以输出 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$
• $1 \le q \le 100$

时空限制

• 时间限制：3 秒
• 空间限制：64 MB