题目描述

某大型物流公司在全国范围内建立了 $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

数据范围

对于 $20\%$ 的数据，满足 $1 \le N, M, K, C_i, L_j \le 100$。

对于 $100\%$ 的数据，满足 $1 \le N \le 250$，$1 \le M \le 10,000$，$1 \le K \le 10,000$，$1 \le C_i \le 100,000$，$1 \le L_j \le 100,000$，$1 \le A_j, B_j, S_i, T_i \le N$。

保证任意两个配送中心之间总能通过若干运输线路连通。