题目描述

物流网络中有 $N$ 个配送中心和 $M$ 条双向运输线路。第 $i$ 个配送中心的维护成本为 $C_i$，每条运输线路都有运输费用。

一条路径的总成本等于：路径上所有运输线路的费用之和，加上路径经过的所有配送中心（包括起点和终点）中的最大维护成本。

共有 $K$ 次询问，每次给出两个配送中心 $S_i,T_i$，求从 $S_i$ 到 $T_i$ 的最小总成本。

输入格式

第一行包含三个整数 $N,M,K$。

接下来 $N$ 行，第 $i$ 行包含一个整数 $C_i$，表示配送中心 $i$ 的维护成本。

接下来 $M$ 行，每行包含三个整数 $A_j,B_j,L_j$，表示配送中心 $A_j$ 与 $B_j$ 之间有一条费用为 $L_j$ 的双向运输线路。

接下来 $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$
• 对于全部数据，$1 \le N \le 250$，$1 \le M,K \le 10000$
• $1 \le C_i,L_j \le 100000$
• $1 \le A_j,B_j,S_i,T_i \le N$
• 保证任意两个配送中心之间都可以互相到达