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

题目描述

马上就要放暑假了！

徐老师决定带着黄老师和石老师出去自驾游，但是临出发的时候徐老师又觉得，自驾游真的好累，但是放出去的话不能食言，于是徐老师决定折中一下。

设徐老师规划的自驾游路线里一共有 $n$ 个城市，编号 $1 \sim n$（不一定要经过所有城市，但是目的地是 $n$ 号城市）

其中徐老师会在路程的前一部分坐火车到达某一个城市 $x$，然后在 $x$ 号城市租一辆车，一直开到 $n$ 号城市，并在 $n$ 号城市直接还车（租车费用以租车城市为准）

形式化的说，徐老师会从 $1$ 号城市出发，先坐火车到达城市 $x$，花费 $value$ 元，然后在 $x$ 号城市租车（租车费用为 $T_x$元 $/$ 天），自驾到 $n$ 号城市，花费 $day$ 天，那么徐老师一共需要花费 $value + T_x * day$ 元

现在徐老师已经统计好了城市之间的一共 $m1$ 条**铁路（只允许坐火车）和 $m2$ 条高速公路（只允许自驾）**的路线

• 第 $i$ 条铁路连接了 $u_i$ 和 $v_i$ 两个城市，从 $u_i$ 号城市坐火车到 $v_i$ 号城市的费用为 $w_i$ 元，从 $v_i$ 号城市坐火车到 $u_i$ 号城市的费用也是 $w_i$ 元。
• 第 $i$ 条高速公路连接了 $u_i$ 和 $v_i$ 两个城市，从 $u_i$ 号城市开车到 $v_i$ 号城市需要 $w_i$ 天，从 $v_i$ 号城市开车到 $u_i$ 号城市也需要 $w_i$ 天。

并且徐老师已经统计好了每个城市租车的价格：第 $i$ 号城市租车的价格为 $T_i$ 元 $/$ 天

但是石老师突然提醒他：由于假期的到来，每个城市的租车价格也在实时的变动！

现在徐老师想在每次租车价格变化时（每次只会有一个城市的价格发生变化，这个变化会影响到后续的计算），计算出他最少需要花费多少钱才能完成这趟路程，从 $1$ 号城市到达 $n$ 号城市。

P.S. 徐老师也可以不坐火车，从 $1$ 号城市直接租车开到 $n$ 号城市；也可以不租车，直接坐火车到达 $n$ 号城市。

输入格式

输入第一行包含一个整数 $n$ 表示有 $n$ 个城市

输入第二行包含 $n$ 个整数，分别表示每个城市的租车价格 $T_i$

接下来输入一行包含一个整数 $m1$ 表示有 $m1$ 条铁路

接下来 $m1$ 行，每行三个整数 $u_i,v_i,w_i$ 描述一条铁路信息，含义如题

接下来输入一行包含一个整数 $m2$ 表示有 $m2$ 条高速公路

接下来 $m2$ 行，每行三个整数 $u_i,v_i,w_i$ 描述一条高速公路信息，含义如题

接下来输入一行包含一个整数 $Q$ 表示租车信息变化的次数

接下来 $Q$ 行每行包含两个整数 $a,b$ 表示 $a$ 号城市的租车价格变化为 $b$ 元 $/$ 天

输出格式

输出 $Q$ 行，每行包含一个整数，表示每次租车价格变化时，徐老师完成旅行的最小花费

数据范围

对于 $15\%$ 的数据：$n,m1,m2,Q \leq 10$

对于 $35\%$ 的数据：$n,m1,m2,Q \leq 50$

对于 $55\%$ 的数据：$n,m1,m2,Q \leq 200$

对于 $75\%$ 的数据：$n,m1,m2,Q \leq 1000$

特别的，有另外 $10\%$ 的数据满足：$m1 = 0$

对于 $100\%$ 的数据：$1 \leq n,Q \leq 200000, 0 \leq m1,m2 \leq 200000, 1 \leq a,u_i,v_i \leq n, 0 \leq T_i,b \leq 10^6$

特别的：对于铁路 $0 \leq w_i \leq 10^9$，对于高速公路有 $0 \leq w_i \leq 10^6$

样例输入

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

样例输出

4
6
9

样例解释

第一次修改后租车价格分别为 $[2,2,3,4]$，徐老师可以选择 $1$ 号城市直接租车，花费 $2$ 天到达 $4$ 号城市，一共花费 $2 * 2=4$ 元

第二次修改后租车价格分别为 $[10,2,3,4]$，徐老师可以选择先坐铁路到达 $2$ 号城市花费 $4$ 元，然后在 $2$ 号城市租车，花费 $1$ 天到 $4$ 号城市，一共花费 $4 + 2 * 1 = 6$ 元

第三次修改后租车价格分别为 $[10,5,3,4]$，徐老师可以选择坐火车先到 $2$ 号城市，再坐火车到达 $4$ 号城市，花费 $4+5=9$ 元