过路费属于最短路径问题

过路费

问题描述

某一天你踏上了前往这个特殊国家的经历。
在这些国家里共有N个城市。
这些城市通过若干条双向的道路相互连接。
每条道路都附带一定的通行费用。
其中每条道路两端的城市也会收取过路费。
经过分析发现：从一个城市到达另一个城市的总花费由两部分组成：一是路径中所有城市中的最大过路费之和（包括起点与终点），二是所有道路的通行费之和。
针对Q次特定查询做出回应时，则需要计算并提供每一次查询中两个城市对之间的最低通达成本。

输入格式

第一行给出两个整数 N 和 M ，分别表示有 N 个城市和 M 条道路连接。
接下来的 N 行数据中每一行都是一个整数 c_i ，代表第 i 个城市的建设成本。
然后是连续的 M 行信息，每一行包含三个整数 x, y, z ，表示城市 x 和城市 y 之间有一条收费为 z 的公路。
接下来的一行是一个整数 Q ，表示将要处理的查询总数。
最后是连续的查询部分，每一行给出两个不相同的整数 x, y ，要求计算从第 x 个城市到第 y 个城市之间的最低通行费用。

输出格式

共 Q 行每行一个整数，第 i 行的整数表示第 i 次询问的答案。

样例输入

3 3
1
3