题目描述

给定一个 $n$ 点 $m$ 边的双向图，第 $i$ 条道路连接了 $u_i$ 与 $v_i$，边权为 $w_i$，第 $i$ 个点的点权为 $c_i$。

给定 $q$ 组询问，第 $i$ 组询问求从 $s_i$ 到 $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$ 组询问的结果。

输入输出样例 #1

输入 #1

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

输出 #1

8 
9

说明/提示

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