题目描述

和所有人一样，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$)。从一个牧场移动到另一个不同牧场的总费用是：所经过的所有小路的路费之和，再加上一个额外的费用——这个费用是沿途经过的所有牧场（包括起点和终点）中，牧场收费的最大值。

耐心的奶牛们希望研究它们的出行选择。它们需要你编写一个程序，接收 $K(1 \le K \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$ 行每行三个整数 $u_i,v_i,w_i$ 代表第 $i$ 条边从 $u_i$ 连到 $v_i$ 边权为 $w_i$。
接下来 $q$ 行每行两个整数 $s_i,t_i$ 代表第 $i$ 组询问求从 $s_i$ 到 $t_i$ 的边权之和与点权的最大值的和的最小值。

输出格式

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

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 

8 
9 

提示

对于 $100\%$ 的数据，$1 \le n \le 250$，$1 \le m \le 10^4$，$1 \le q \le 10^4$。