1116. [郑州培训2012] 凯旋

【背景】

当Caesar，Pearl和他们的宠物们完成了种玫瑰的任务之后，已是黄昏。

Pearl对Caesar说：“哎呀，肚子好饿呀，Caesar我们的晚餐由谁来做呀？”

“当然由我来搞定了！”Caesar拍拍胸脯说。“但今天我也很累了，不如我们就在回家的路上找一个地方野餐吧。”

“好呀好呀！”同样工作了一天的宠物们高兴地欢呼起来。

Caesar的脸色变得严峻起来。他知道这些宠物是不好养的。宠物们会选一个最贵的地方进行野餐。

【题目描述】

Caesar专注地看着回家的地图，地图上标有n（n<=200）个野餐点和野餐点之间的直达道路以及每条道路的过路费。Caesar还知道在每一个野餐点野餐的费用。你的程序会收到一些询问（i，j）满足i<>j。对于Caesar他们当前在i野餐点，要回到位于j野餐点的家，回家路线由Caesar决定，Caesar要求你求出最小费用。（费用=过路费+路径上最贵的野餐点的费用，起点和终点也有可能成为野餐的地方）

【输入格式】

第一行n，m表示结点数和边数。边是双向的。接下来一行n个数，第i个数表示在i点野餐的费用。接下来m行，每行三个数i，j，k，表示i点与j点有一条直达路线，过路费为k。再下来一个数t单独一行，表示有t(1<=t<=40000)个询问。最后t行，每行2个数i，j，表示询问（i，j）。

【输出格式】

 输出t行，依次为每个询问的答案。每个答案都不会超过2^31-1.

【样例输入】

5 7
3 4 5 4 3
1 2 6
2 3 2
3 4 2
4 5 6
1 5 10
1 4 7
2 5 7
5
1 3
2 4
3 5
1 4
2 3

【样例输出】

13
9
13
11
7

【来源】

中小学电脑报 NOI导刊 NOIP2012河南省实验中学培训 Day4 Exercise Problem 5