时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一天你来到了一个奇怪的国家，它有 \(N\) 个城市，城市之间有若干条双向道路连接，每条道路都有一定的费用，经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用（包括起点和终点）加上路径上所有的道路的费用。给出 \(Q\) 次询问，分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。

【输入格式】

　　第一行两个整数 \(N，M\)，表示有 \(N\) 个城市 \(M\) 条道路。
　　接下来 \(N\) 行每行一个整数，表示城市的费用 \(c_i\)。
　　接下来 \(M\) 行每行三个整数，\(x，y，z\)，表示城市 \(x\) 和城市 \(y\) 间有一条费用为 \(z\) 的道路。
　　接下来一行一个整数 \(Q\)，表示询问次数。
　　接下来 \(Q\) 行每行两个整数 \(x，y\)（\(x\) 不等于 \(y\)），表示询问从城市 \(x\) 到城市 \(y\) 的最小花费。

【输出格式】

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

【输入输出样例】

　Input

3 3
1
3
2
1 2 1
2 3 1
1 3 3
2
1 3
1 3

　Output

5
5

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤N≤10\)，\(1≤M≤20\)，\(1≤Q≤20\)
　　对于 \(60\%\) 的数据，\(1≤N≤200\)，\(1≤M≤4000\)，\(1≤Q≤100\)
　　对于 \(100\%\) 的数据，\(1≤N≤300\)，\(1≤M≤40000\)，\(1≤Q≤100000\)，\(1≤c_i≤100000\)，\(1≤z≤1000\)

【来源】

　　Mr.he