Description

给一个图,拥有如下性质: 1.边有向 2.不一定连通 3.每两点之间可有无数条边 4.点可有到自己的边 5.每个点和每条边有一个非负权值 点 A 到点 B 的某条路径的权值定义为 该路径上所有边的权值的和 + 该路径上所有点的权值的最大值 对于若干询问 求出 A 到 B 的最短路径

Input

输入包含多组数据,每组数据第一行为三个整数 n m q,表示图的点数,边数和询问数 接下来一行,有 n 个整数,分别为 n 个点的权值 接下来 m 行,每行三个整数 a b c 表示 a 到 b 的权值为 c 接下来 q 行,每行两个整数 a b, 表示询问 a 到 b 的最短路径 如果不存在 a 到 b 的路径,输出 -1 (1 <= n <= 100 , 1 <= m <= 20000 , 1 <= q <= 10000 ,1 <= 权值 <= 10000)

Output

每组数据输出 q 行,每行为一个对应的询问结果

Sample Input

7 7 2 1 1 1 1 1 1 100 0 1 10 1 2 10 2 3 10 3 4 10 0 5 1 5 6 1 6 4 1 0 4 4 0

Sample Output

41 -1

Hint

Special for UESTC! Best wishes to UESTC and SCU!

Author

windy7926778