【题目描述】

小A从历史书上了解到，从前有一个王国，它有N个城堡，M条王国道路，每条王国道路连接着两个城堡，经过这条道路所需的时间为wi。国王想要将军护送一批物品，从城堡S到城堡T，国王会为将军规划一条路径，将军会严格按照国王的要求走。将军虽能力过人，但有沉迷享乐的毛病。他会选择他能经过的最繁华的一个城堡在那里享乐，并耽误ci的时间。国王想要让物品尽快送达，并且总共有Q次护送。

【输入格式】

第一行两个整数N，M，表示有N个城堡M条王国道路； 接下来N行每行一个正整数，表示城堡的繁华系数ci； 接下来M行每行三个正整数，ui,vi,wi表示一条王国道路； 接下来一行一个整数Q，表示护送次数； 接下来Q行每行两个整数s，t（s != t），表示派将军从城堡S护送物品到城堡T所需要的最短时间。

【输出格式】

共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≤5N≤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。

保证城堡之间可以互达。

时间限制：2S 空间限制：512M