题目描述

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

有一天，约翰宣布奶牛走路要收过路费，只要奶牛走过第 i 条道路，就要收费 Li 元。此外，约翰还要求每头奶牛购买牌照，他为每片草地设置了牌照标准，如果奶牛购买的牌照价格低于某片草地的标准，她将被禁止进入那片草地。第 i 片草地的牌照标准为 Ci。

新政策一出，奶牛们敢怒不敢言，有 Q 头奶牛向你咨询最省钱的走路办法，第 i 头奶牛要从草地 Si 走到 Ti。请你帮她们算算，选择什么样的路线才能最省钱？

输入格式

第一行：三个整数 N ，M 和 Q，1 ≤ N ≤ 250; 1 ≤ M ≤ 10000; 1 ≤ Q ≤ 10000

• 第二行到第 N + 1 行：第 i + 1 行有一个整数 Ci，1 ≤ Ci ≤ 10^6

• 第 N + 2 行到第 N + M + 1 行：第 i + 1 行有三个整数 Ai，Bi 和 Li，1 ≤ Ai ; B i ≤ N ,1 ≤ Li ≤ 10^6

• 第 N + M +2 行到第 N + M + Q +1 行：第 i + N + M +1 行有两个整数 Si 和 Ti，1 ≤ Si,Ti ≤ N

输出格式

第一行到第 Q 行：第 i 行有一个整数，表示从 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 到4 的最好办法是1→3→5→4，从2 到3 的最好办法是2→5→3