UVA11367 Full Tank?

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

对于 $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$。