题目描述

\\n\\n有 N 个城市（编号 0、1…N−1）和 M 条道路，构成一张无向图。
\\n在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。
\\n现在你需要回答不超过 100 个问题，在每个问题中，请计算出一架油箱容量为 C 的车子，从起点城市 S 开到终点城市 E 至少要花多少油钱？
\\n注意：假定车子初始时油箱是空的。
\\n\\n

输入格式

\\n\\n第一行包含两个整数 N 和 M。
\\n第二行包含 N 个整数，代表 N 个城市的单位油价，第 i 个数即为第 i 个城市的油价 pi。
\\n接下来 M 行，每行包括三个整数 u,v,d，表示城市 u 与城市 v 之间存在道路，且车子从 u 到 v 需要消耗的油量为 d。
\\n接下来一行包含一个整数 q，代表问题数量。
\\n接下来 q 行，每行包含三个整数 C、S、E，分别表示车子油箱容量 C、起点城市 S、终点城市 E。
\\n\\n

输出格式

\\n\\n对于每个问题，输出一个整数，表示所需的最少油钱。
\\n如果无法从起点城市开到终点城市，则输出 impossible。
\\n每个结果占一行。
\\n\\n

样例

\\n

Statistics

Submission Statistics

【例】装满的油箱

Information

Status

Development

Support

SIGN IN