题目描述

有 $N$ 个城市和 $M$ 条道路，构成一条无向图。

在每个城市都有一个加油站，不同的加油站的价格都不一样。

通过一条道路的油耗就是该道路的边权。

现在你需要回答 $q$ 个问题，在每个问题中，请计算出一辆油箱容量为 $c$ 的，起始时油箱为空的车子，从起点 $s$ 到终点 $e$ 至少要花多少钱。

输入格式

第一行两个整数城市数 $N(1 \leq N \leq 1000)$，道路数$M(0 \leq M \leq 10000)$。

接下来 $N$ 个整数为每个城市的油的价格 $p_i(1 \leq p_i \leq 100)$。

接下来 $M$ 行每行三个整数$u,v,d$，描述 $u$ 城市到 $v$ 城市 $(0 \leq u,v < N)$ 有一条油耗为 $d(1 \leq d \leq 100)$ 的道路。

接下来的一个整数 $q(1 \leq q \leq 100)$ 为询问数量。

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

题目满足 $1 \leq c \leq 100$。

输出格式

对于每个询问，每一行回答一个数，为至少花费的钱。如果不能到达，输出 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