暂无测试数据。

Description

球国有 \(n\) 个城市，编号为 \(1\) 到 \(n\)，彼此之间由 \(m\) 条双向道路连接，第 \(i\) 条道路连接了城市 \(A_i\) 和 \(B_i\)，两个城市之间可能有多条道路，但没有道路会连接同一个城市，现有的道路可以保证任意两个城市都是连通的。
有一天，球球国王宣布司机驾车过路要收过路费，只要驾车走过第 \(i\) 条道路，就要收费 \(L_i\) 元。此外，球球国王还要求每个司机购买通行证，它为每个城市设置了通行证费用标准，如果司机购买的通行证价格低于某个城市的费用标准，则他不能进入那个城市。第 \(i\) 个城市的通行证费用标准为 \(C_i\)。
新政策一出，司机们都是敢怒不敢言，有 \(Q\) 个司机向你咨询最省钱的驾车行路办法，第 \(i\) 个司机要从城市 \(S_i\) 到城市 \(T_i\)。请你帮他们算算，选择什么样的路线才能最省钱？

---

Input

第 \(1\) 行：三个整数 \(n\)，\(m\) 和 \(Q\)，含义如题目描述。
第 \(2\) 行到第 \(n+1\) 行：第 \(i+1\) 行有一个整数 \(C_i\)。
第 \(n+2\) 行到第 \(n+m+1\) 行：第 \(i+1\) 行有三个整数 \(A_i\)，\(B_i\) 和 \(L_i（\)1\le A_i,B_i\le n\(）。
第 \)n+m+2\( 行到第 \)n+m+Q+1\( 行：第 \)i+N+M+1\( 行有两个整数 \)S_i\( 和 \)T_i\(（\)1\le S_i,T_i\le n$）。

---

Output

第 \(1\) 行到第 \(Q\) 行：第 \(i\) 行有一个整数，表示从 \(S_i\) 到 \(T_i\) 的最低费用是多少。

Sample

Sample Input

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

Sample Output

8
9

Sample Explanation

最好办法分别是 \(1 \→ 3 \→ 5 \→ 4\) 和 \(2 \→ 5 \→ 3\)。

---

Hint

对于 \(100\%\) 的数据：\(1\le n\le 250\)，\(1\le M\le 10000\)，\(1\le Q\le 10000\)，\(1\le C_i\le 10^6\)，\(1\le L_i\le 10^6\)。