某大型物流公司在全国范围内建立了 N 个配送中心，这些配送中心通过 M 条双向运输线路互相连接，每条线路都有一定的运输费用。为了提高网络安全性和运营效率，每个配送中心还设置了一项固定的安全维护成本。
具体地，第 i 个配送中心的安全维护成本为 C_i，而第 j 条运输线路连接了配送中心 A_j 和 B_j，其运输费用为 L_j。
当从一个配送中心运输物资到另一个配送中心时，总运输成本由两部分组成：
经过的所有运输线路的费用总和。
运输过程中经过的所有配送中心（含起止点）中安全维护成本的最大值。
公司需要对物流网络进行分析，回答 K 个运输路径的最低成本问题。第 i 个查询要求计算从配送中心 S_i 到配送中心 T_i 的最低运输成本。
第 1 行包含三个整数 N, M, K，分别表示配送中心的数量、运输线路的数量和查询的数量。
接下来的 N 行，第 i+1 行包含一个整数 C_i，表示第 i 个配送中心的安全维护成本。
接下来的 M 行，每行包含三个整数 A_j, B_j, L_j，表示第 j 条运输线路连接配送中心 A_j 和 B_j，运输费用为 L_j。
接下来的 K 行，每行包含两个整数 S_i, T_i，表示第 i 个查询需要计算从配送中心 S_i 到配送中心 T_i 的最低运输成本。
输出共 K 行，每行一个整数，表示从 S_i 到 T_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
7 9 5 2 5 8 3 8 6 9 4 3 2 2 7 3 7 1 9 7 5 12 6 7 5 2 4 4 5 1 8 3 1 3 5 2 1 7 3 3 5 3 4 4 1 2 6
18 15 10 13 17
20 42 20 25 80 17 92 18 15 73 72 10 93 26 56 62 53 14 63 37 98 100 63 12 1 90 14 10 18 20 19 29 14 2 19 17 10 38 14 16 55 20 9 37 9 5 49 7 3 68 19 9 12 11 10 89 8 17 28 1 18 34 14 1 56 17 13 11 14 4 12 8 19 37 2 1 27 13 14 5 7 6 35 5 2 33 6 14 27 9 2 72 5 14 15 16 3 70 17 3 91 4 9 39 5 13 25 10 19 12 6 4 33 1 10 37 20 7 65 3 20 96 2 13 87 5 10 83 17 19 68 6 17 53 2 4 32 15 4 21 3 5 34 12 19 37 20 16 17 8 16 8 1 4 1 9 16 10 17 16 20 14 8 10 3 14 18 16 14 16 9 5 11 9 18 11 7 13 8 7 2 6 17 20 11 17 20 8 9
171 170 150 117 127 80 116 160 178 118 117 215 195 262 111 161 90 230 151 149
物流网络包括 5 个配送中心，其安全维护成本分别为：
运输线路如下：
对于第一个查询，从配送中心 1 到配送中心 4 的最低运输成本为 8，路径为 1 \to 3 \to 5 \to 4，其线路费用为 2 + 1 + 1 = 4，最大安全维护成本为 4，因此总费用为 4 + 4 = 8。
对于第二个查询，从配送中心 2 到配送中心 3 的最低运输成本为 9，路径为 2 \to 5 \to 3，其线路费用为 3 + 1 = 4，最大安全维护成本为 5，因此总费用为 4 + 5 = 9。
对于 20\% 的数据，满足 1 \le N,M,K,C_i,L_j \le 100。
对于 100\% 的数据，满足 1 \leq N \leq 250，1 \leq M \leq 10,000，1 \leq K \leq 10,000，1 \leq C_i \leq 100,000，1 \leq L_j \leq 100,000，1 \leq A_j, B_j, S_i, T_i \leq N。
保证任意两个配送中心之间总能通过若干运输线路连通。