Full Tank?

### 题目描述 有 $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`。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2352 [PDF](https://uva.onlinejudge.org/external/113/p11367.pdf) 



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