该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

国庆假期时的旅游也太不快乐了！不管到什么景点，除了看人还是看人！

于是徐老师决定趁着大家过完假期都上班了，再出去玩一趟！

但是由于国庆假期已经花了太多钱，囊中羞涩的徐老师决定绿色出行——先坐铁路再租车（其实就是贫穷）

现在徐老师已经整理出了 $n$ 个城市之间的路线，其中徐老师所在的城市为 $1$ 号城市，目的地是 $n$ 号城市

其中城市之间存在 $len1$ 条城际铁路和 $len2$ 条高速公路

第 $i$ 条城际铁路连接着 $u_i,v_i$ 两个城市（双向），坐高铁的 费用 为 $c_i$ 元

第 $i$ 条高速公路连接着 $u_i,v_i$ 两个城市（双向），需要花费 时间 为 $c_i$ 小时

而徐老师决定先坐高铁再租车，以此来到达目的地 $n$ 号城市

也就是说徐老师会设定一个目的地 $x$，先通过城际铁路从 $1$ 号城市到达 $x$ 号城市，然后在 $x$ 号城市租一辆车开往 $n$ 号城市，在游玩以后再把车从 $n$ 号城市开回 $x$ 号城市归还，然后结束旅行

其中，在第 $i$ 号城市租车的费用为每小时 $a_i$ 元，并且徐老师需要把车开回 $i$ 号城市归还，但是在徐老师到达 $n$ 号城市以后，他在 $n$ 号城市游玩时不会使用这辆车，则不需要付租车费，也就是说徐老师最终需要付的租车费为： （$x$ 号城市到达 $n$ 号城市的时间 $+ n$ 号城市到达 $x$ 号城市的时间） $* a_x$

现在徐老师想知道，他最少需要花费多少钱来完成这趟旅程？

P.S.1 高铁是可以换乘的，例如可以从 $a$ 城市坐到 $b$，再从 $b$ 城市换一条城际铁路到达 $c$

P.S.2 租车不可以换车，选定在 $x$ 号城市租车后，中途不能换车

输入格式

输入第一行包含三个整数 $n,len1,len2$，含义如题

接下来一行包含$n$ 个整数 $a_1,a_2 \dots a_n$，含义如题。

接下来 $len1$ 行，每行三个整数 $u_i,v_i,c_i$，表示一条城际铁路的信息。

接下来 $len2$ 行，每行三个整数 $u_i,v_i,c_i$，表示一条高速公路的信息。

接下来一行输入一个整数 $T$ 表示 $T$ 次询问

接下来 $T$ 行，每行两个整数 $x_i,y_i$，表示将城市 $x_i$ 的租车费用改成每小时 $y_i$ 元（修改具有连续性，第 $i$ 次的修改是在第 $i - 1$ 次修改的基础上继续修改）

输出格式

对于每次询问，输出一个整数表示徐老师最少花费多少钱

数据范围

对于所有数据满足：$a_i \leq 10^6$，且城际铁路的 $c_i\leq 10^9$ 高速公路的 $c_i \leq 10^6$

样例输入1

4 3 3
2 5 3 4 
2 1 5
4 1 10
3 4 6
4 2 1
2 1 2
4 1 2
3
2 2
1 10
2 5

样例输出1

8
9
10

样例解释1

第一次询问的租车费用分别为 $[2,2,3,4]$，徐老师可以直接在 $1$ 号城市租车到达 $4$ 号城市，费用为 $(2 + 2) * 2 = 8$ 元

第二次询问的租车费用分别为 $[10,2,3,4]$，徐老师可以直接先坐城际铁路到 $2$ 号城市，然后在 $2$ 号城市租车前往 $4$ 号城市，费用为 $5 + (1+1) * 2 = 9$ 元

第三次询问的租车费用分别为 $[10,5,3,4]$，徐老师可以直接坐城际铁路到 4 号城市，花费 $10$ 元

样例输入2

5 4 4
2 2 2 2 2
1 2 8
2 3 7
3 4 9
4 5 11
3 5 1
3 1 2
2 4 3
4 1 5
4
2 5
1 7
3 1
3 8

样例输出2

12
19
17
31