题目描述

跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生 财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都 要向农夫约翰上交过路费。 农场中由$\red{N（}$$\red{1 <= N <= 250）}$片草地（标号为$\red{1}$到$\red{N）}$，并且有$\red{M（}$$\red{1 <= M <= 10000）}$ 条 双向道路连接草地$\red{A_j}$和$\red{B_j（}$$\red{1 <= A_j <= N}$; $\red{1 <= B_j <= N）}$。

奶牛们从任意一片草 地出发可以抵达任意一片的草地。$\red{FJ}$已经在连接$\red{A_j}$和$\red{B_j}$的双向道路上设置一个过路费$\red{L_j （}$$\red{1 <= L_j <= 100,000）}$。 可能有多条道路连接相同的两片草地，但是不存在一条道路连接一片草地和这片草地本身。最 值得庆幸的是，奶牛从任意一篇草地出发，经过一系列的路径，总是可以抵达其它的任意一片 草地。

除了贪得无厌，叫兽都不知道该说什么好。$\red{FJ}$竟然在每片草地上面也设置了一个过路费$\red{C_i （}$$\red{1 <= C_i <= 100000）}$。从一片草地到另外一片草地的费用，是经过的所有道路的过路 费之和，加上经过的所有的草地（包括起点和终点）的过路费的最大值。 任劳任怨的牛们希望去调查一下她们应该选择那一条路径。

她们要你写一个程序，接受$\red{K（}$$\red{1 <= K <= 10,000）}$个问题并且输出每个询问对应的最小花费。第$\red{i}$个问题包含两个数字$\red{s_i }$和$\red{t_i（}$$\red{1 <= s_i <= N}$; $\red{1 <= t_i <= N}$; $\red{s_i != t_i）}$，表示起点和终点的草地。 考虑下面这个包含$\red{5}$片草地的样例图像:

从草地$\red{1}$到草地$\red{3}$的道路的"边过路费"为$\red{3，}$草地$\red{2}$的"点过路费"为$\red{5}$。 要从草地$\red{1}$走到草地$\red{4，}$可以从草地$\red{1}$ 走到草地$\red{3}$再走到草地$\red{5}$最后抵达草地$\red{4}$。如果这么走的话， 需要的"边过路费"为$\red{2+1+1=4，}$需要的点过路费为$\red{4（}$草地$\red{5}$的点过路费最大），所以总的花 费为$\red{4+4=8}$。

而从草地$\red{2}$到草地$\red{3}$的最佳路径是从草地$\red{2}$出发，抵达草地$\red{5，}$最后到达草地$\red{3}$。这么走的话，边 过路费为$\red{3+1=4，}$点过路费为$\red{5，}$总花费为$\red{4+5=9}$。

输入格式

第$\red{1}$行: 三个空格隔开的整数: $\red{N, M}$和$\red{K }$

第$\red{2}$到第$\red{N+1}$行: 第$\red{i+1}$行包含一个单独的整数: $\red{C_i }$

第$\red{N+2}$到第$\red{N+M+1}$行: 第$\red{j+N+1}$行包含$\red{3}$个由空格隔开的整数: $\red{A_j, B_j}$和$\red{L_j }$

第$\red{N+M+2}$倒第$\red{N+M+K+1}$行: 第$\red{i+N+M+1}$行表示第$\red{i}$个问题，包含两个由空格隔开的整数$\red{s_i }$和$\red{t_i}$

输出格式

第$\red{1}$到第$\red{K}$行: 第$\red{i}$行包含一个单独的整数，表示从$\red{s_i}$到$\red{t_i}$的最小花费。

样例

输入样例

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