【题意】

约翰家有 $N$ 片草地，编号为 $1$ 到 $N$，彼此之间由 $M$ 条双向道路连接，第 $i$ 条道路连接了 $A_i$ 和 $B_i$，两片草地之间可能有多条路径，但没有道路会连接同一对草地。现有的道路可以保证任意两片草地都是连通的。

有一天，约翰宣布奶牛走路要收过路费，只要奶牛走过第 $i$ 条道路，就要收费 $L_i$ 元。

此外，约翰还要求每头奶牛购买牌照，他为每片草地设置了牌照标准，如果奶牛购买的牌照价格低于某片草地的标准，她将被禁止进入那片草地。第 $i$ 片草地的牌照标准为 $C_i$。

新政策一出，奶牛们敢怒不敢言，有 $Q$ 头奶牛向你咨询最省钱的走路办法，第头奶牛要从草地 $S_i$ 走到 $T_i$。

请你帮她们算算，选择什么样的路线才能最省钱?

【输入格式】

第一行三个整数 $N \ M \ Q \ (1 \le N \le 250,1 \le M \le 10000,1 \le Q \le 10000)$

下来 $N$ 个整数 $C_i \ (1 \le C_i \le 10^6)$

下来 $M$ 行，第 $i$ 行有三个整数 $A_i \ B_i \ L_i \ (1 \le A_i,B_i \le N, 1 \le L_i \le 10^6)$

下来 $Q$ 行，第 $i$ 行有两个整数 $S_i \ T_i \ (1 \le S_i,T_i \le N)$

【输出格式】

Q 行，每行一个整数，表示从 Si到 Ti的最低费用是多少.

【样例输入】

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

【样例解释】

最好办法分别是 1 -》3 -》 5-》 4 和2 -》5 -》3