P2966 [USACO09DEC] Cow Toll Paths G

和所有人一样，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$ 组询问的结果。

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