题目描述

有 $N$ 个城市和 $M$ 条双向道路构成一个无向图，通过一条道路的油耗就是该道路的边权。

现在你需要回答 $q$ 个问题，在每个问题中，你需要求出一辆油箱容量为 $c$ 且起始时油箱为空的车从 $s$ 城市到 $e$ 城市至少要花多少钱，或报告无解。

输入格式

第一行两个整数 $N,M$，分别表示城市数和道路数。

第二行 $N$ 个用空格分隔的整数 $p_1,p_2,\dots,p_N$，分别表示每个城市每单位燃油的价格。

接下来 $M$ 行，每行三个整数 $u,v,d$，表示 $u$ 城市和 $v$ 城市之间有一条油耗为 $d$ 的双向道路。

接下来一行一个整数 $q$，表示询问数量。

接下来的 $q$ 行每行三个整数 $c,s,e$，表示询问一辆容量为 $c$ 的车从 $s$ 城市到 $e$ 城市至少要花多少钱。

输出格式

对于每个询问，输出一行一个整数，表示至少花费的钱。特别地，如果容量为 $c$ 的车无法从 $s$ 城市到 $e$ 城市，输出一行 impossible。

输入输出样例 #1

输入 #1

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

输出 #1

170
impossible

说明/提示

对于 $100\%$ 的数据，$1 \leq N \leq 10^3$，$0 \leq M \leq 10^4$，$1 \leq p_i,d,c \leq 100$，$0 \leq u,v,s,e < N$，$1 \leq q \leq 100$。