题目描述

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

数据范围

• $1≤N≤1000$
• $1≤M≤10000$
• $1≤p_i≤100$
• $1≤d≤100$
• $1≤C≤100$
• $1≤q≤100$

来源

• POJ3635
• 算法竞赛进阶指南