题目描述

和所有人一样，FJ 总是在想方设法增加他的收入。为此，他在农场的牛群穿行于各个牧场之间时，设置了一系列收费站。

奶牛们在 $N(1 \le N \le 250)$ 个牧场（编号为 $1 \dots N$）之间移动。农场中有 $M(1 \le M \le 10,000)$ 条双向小路连接不同的牧场对 $A_j$ 和 $B_j$ ($1 \le A_j \le N; 1 \le B_j \le N$)。FJ 为连接牧场 $A_j$ 和 $B_j$ 的路径分配了路费 $L_j$ ($1 \le L_j \le 100,000$)。

虽然同一对牧场之间可能存在多条小路，但小路永远不会将牧场与自身相连。最棒的是，奶牛总能通过一系列小路从任何一个牧场移动到另一个牧场。

在一种只能被描述为贪婪的行为中，FJ 还为每个牧场分配了过路费 $C_i$ ($1 \le C_i \le 100,000$)。从一个牧场移动到另一个不同牧场的总费用是：所经过的所有小路的路费之和，再加上一个额外的费用——这个费用是沿途经过的所有牧场（包括起点和终点）中，牧场过路费的最大值。

耐心的奶牛们希望研究它们的出行选择。它们需要你编写一个程序，接收 $Q(1 \le Q \le 10,000)$ 个查询并输出每个查询指定的行程的最小费用。查询 $i$ 是一对数字 $s_i$ 和 $t_i$ ($1 \le s_i \le N; 1 \le t_i \le N; s_i \neq t_i$)，分别指定起点和终点牧场。

输入格式

第一行三个整数 $N,M,Q$ 代表点数，边数与询问数。
接下来 $N$ 行每行一个整数 $C_i$ 代表第 $i$ 个点的点权。
接下来 $M$ 行每行三个整数 $A_i,B_i,L_i$ 代表第 $i$ 条边从 $A_i$ 连到 $B_i$ 边权为 $L_i$。
接下来 $Q$ 行每行两个整数 $s_i,t_i$ 代表第 $i$ 组询问求从 $s_i$ 到 $t_i$ 的边权之和与点权的最大值的和的最小值。

输出格式

$Q$ 行每行一个整数，代表第 $i$ 组询问的结果。

输入样例 #1

5 7 2 
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 4 
2 3 

输出样例 #1

8 
9 

输入样例 #2

2 1 1
52096
29833
1 2 36614
1 2

输出样例 #2

88710

输入样例 #3

3 3 2
32126
66336
79482
1 2 34079
2 3 82446
1 3 36949
3 2
2 3

输出样例 #3

150510
150510

数据范围

奶牛们在 $N(1 \le N \le 250)$ 个牧场（编号为 $1 \dots N$）之间移动。

农场中有 $M(1 \le M \le 10,000)$ 条双向小路连接不同的牧场对 $A_j$ 和 $B_j$ ($1 \le A_j \le N; 1 \le B_j \le N$)。

FJ 为连接牧场 $A_j$ 和 $B_j$ 的路径分配了路费 $L_j$ ($1 \le L_j \le 100,000$)。

在一种只能被描述为贪婪的行为中，FJ 还为每个牧场分配了过路费 $C_i$ ($1 \le C_i \le 100,000$)。

它们需要你编写一个程序，接收 $Q(1 \le Q \le 10,000)$ 个查询并输出每个查询指定的行程的最小费用。

查询 $i$ 是一对数字 $s_i$ 和 $t_i$ ($1 \le s_i \le N; 1 \le t_i \le N; s_i \neq t_i$)。

对于 $100\%$ 的数据，$1 \le N \le 250$，$1 \le M \le 10^4$，$1 \le Q \le 10^4$。