有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,分别表示车子油箱容量、起点城市 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≤pi≤100 1≤d≤100 1≤C≤100