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

---

【题目描述】

　　小H谋得一份兼职——货车司机，从此以后他将会开着货车穿行在C国的各大城市之间。

　　C国中有 \(n\) 座城市（编号为 \(1..n\)），并且有 \(m\) 条双向公路，每条公路连接两座不同的城市。货车从任意一座城市出发都可以抵达任意另一座城市。在每条公路上，都有一个收费站，通过的车辆需要交纳一定过路费。可能有多条公路连接相同的两座城市。

　　为了增加财政收入，C国还在每座城市也设置了收费站。并且规定，车辆从一座城市到另一座城市的费用是，所经过公路费用和，加上所经过的城市中费用的次大值（这里的次大可以和最大相同，但是城市不同）。

　　现在小H告诉你今年 \(k\) 次业务运送货物的起点、终点城市列表，请你帮忙计算，每次业务需要交纳的最低过路费。

【输入格式】

　　第一行包含三个用一个空格隔开的整数：\(n,m,k\)。其意义如题目描述。
　　第 2 到第 \(n+1\) 行：第 \(i+1\) 行包含一个单独的整数 \(c(1≤c≤100000)\)，表示城市 \(i\) 的费用。
　　接下来的 \(m\) 行,每行包含三个整数 \(a,b,w\)，表示一条公路连接城市 \(a\) 和城市 \(b（1≤a,b≤n）\)，其过路费为\(w（1≤w≤100000）\)。
　　最后的 \(k\) 行，每行包含两个整数：\(s,t\)，表示一次业务的起点和终点，保证 \(1≤s,t≤n\) 且 \(s!=t\)。

【输出格式】

　　共 \(k\) 行，每行一个整数，表示从城市 \(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

4
7
8

【输入输出样例解释】

　　包含5个城市的样例图形如下：

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

【数据限制】

　　对于 \(20\%\) 的数据，\(1≤n≤10\)，\(1≤m≤20\)。
　　对于 \(20\%\) 的数据，\(1≤n≤100\)，\(1≤m≤5000\)。
　　对于 \(20\%\) 的数据，\(1≤n≤250\)，\(1≤m≤10000\)，\(1≤k≤10000\)，其中有 50% 的数据点权没有重复。

【来源】

　　Mr.he