该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
有一天你来到了一个奇怪的国家，它有N个城市，城市之间有若干条双向道路连接，每条道路都有一定的费用，经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用（包括起点和终点）加上路径上所有的道路的费用。给出Q次询问，分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。
【输入格式】
第一行两个整数N，M，表示有N个城市M条道路。
接下来N行每行一个整数，表示城市的费用ci。
接下来M行每行三个整数，x，y，z，表示城市x和城市y间有一条费用为z的道路。
接下来一行一个整数Q，表示询问次数。
接下来Q行每行两个整数x，y（x不等于y），表示询问从城市x到城市y的最小花费。
【输出格式】
共Q行每行一个整数，第i行的整数表示第i次询问的答案。
【样例输入】
3 3
1
3
2
1 2 1
2 3 1
1 3 3
2
1 3
1 3
【样例输出】
5
5
【数据规模】
对于30%的数据，N<=10，M<=20，Q<=5。
对于60%的数据，N<=200，M<=4000，Q<=100。
对于100%的数据，N<=300，M<=40000，Q<=100000，1<=ci<=100000，1<=z<=1000。