#27 「 最短路 」

统计

给一张n个点,m条边的有向图G。

每个点有点权$v_i$, 每条边有边权$m_i$。

询问q次, 每次询问两个点从u到v如下定义的最短路。

最短路的定义是所有从u到v路径如下定义的权值的最小值。

一条从 u 到 v 路径的权值为路径上的边权和 + 路径经过点的最大点权 值 (包括 u,v)。

若没有从 u 到 v 的路径, 输出-1。

输入格式

第一行三个整数n,m,q。

接下来一行n个整数,表示点权$v_i$。

接下来每行三个整数x,y,z,表示有一条从x到y,边权为z的边。

接下来q行,每行两个整数u,v,表示询问从u到v的题目中所述的最短路。

输出格式

输出共q行,每行一个整数表示答案。

样例数据

input

4 4 2
1 2 5 8
1 2 2
2 3 3
1 4 1
4 3 1
1 3
2 4

output

10
-1

数据规模与约定

$n \le 400, m\le n^2, q \le 60000, 0\le v_i, m_i \le 10^5$。

时间限制:1s

空间限制:512MB

Author: zrt