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

说明/提示

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