测试数据来自 system/2037

作业已超过截止时间，您无法递交本题目。

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

---

【题目描述】

　　C国中有 \(n\) 个城镇（编号为 \(1..n\) ），并且有 \(m\) 条双向道路连接城镇 \(a\) 和 \(b\) 。卡车从任意一个城镇出发可以抵达任意一个城镇。每一条双向道路上设置一个过路费 \(w\)。可能有多条道路连接相同的两个城镇，但是不存在一条道路连接一个城镇和这个城镇本身。

　　除了道路要收费外，经过每个城镇也有过路费 \(c\)。从一个城镇到另一个城镇的费用，是经过的所有道路的费用之和，加上经过的所有城镇 （包括起点和终点）的过路费的最大值。

　　卡车司机们希望你写一个程序，接受 \(q\) 个问题并且输出每个询问对应的最小花费。第 \(k\) 个问题包含两个数字 \(s,t\)，表示起点和终点城镇。

【输入格式】

　　第一行包三个用空格隔开的整数：\(n,m,q\)。
　　第二行到第 \(n+1\) 行：第 \(i+1\) 行包含一个单独的整数 \(c\)，表示第 \(i\) 个城镇的费用。
　　第 \(n+2\) 行到第 \(n+m+1\) 行：第 \(j+n+1\) 行包含 \(3\) 个用空格隔开的整数：\(a,b,w\)，表示一条道路 \((a,b)\) 的费用为 \(w\) 。
　　第 \(n+m+2\) 到第 \(n+m+q+1\) 行：第 \(i+n+m+1\) 行表示第 \(i\) 个问题，包含两个用空格隔开的整数 \(s\) 和 \(t\)（\(1≤s,t≤n\) 且 \(s≠t\)），表示一条询问的起点和终点。

【输出格式】

　　输出 \(q\) 行：第 \(i\) 行包含一个整数，表示从 \(s\) 到 \(t\) 的最小花费。

【输入输出样例】

　Input

5 7 3
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 3
1 4
2 3 

　Output

5
8
9

【输入输出样例解释】

　　包含 5 个城镇的样例图像：

　　城镇1 到城镇3 的道路的“边过路费”为2，城镇3 的“点过路费”为 3。所以总的花费为 2 + 3 = 5 。
　　要从城镇1 走到城镇4 ，可以从城镇1走到城镇3 再走到城镇5 最后到达城镇4 。如果这么走的话，需要的“边过路费”为 2 + 1 + 1 = 4，需要的点过路非为 4（城镇5 的点过路费最大），所以总的花费为 4 + 4 = 8。
而从城镇2 走到城镇3 的最佳路径是从城镇2 出发，抵达城镇5，最后到达城镇3，这么走的话，边过路费为 3 + 1 = 4，点过路费为 5，总花费为 4 + 5 = 9。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤250\)，\(1≤m≤10000\)，\(1≤k≤10000\)，\(1≤c,w≤100000\)。

【来源】

　　Mr.he