由于幻想乡的铁路系统经常拥堵,作为一名热情的工程师,Kawasiro Nitori 计划修建更多铁路来缓解拥堵。
幻想乡有$$$n$$$站,编号从$$$1$$$到$$$n$$$和$$$m$$$双向铁路。每条双向铁路连接两个不同的车站,并且具有正整数长度$$$d$$$。没有两条双向铁路连接相同的两个车站。此外,可以使用这些铁路从任何车站前往任何其他车站。在这$$$n$$$站中,$$$1$$$站是主站。您只需乘坐双向铁路即可从任何其他车站到达任何车站。
由于技术限制,Nitori 只能建造单向铁路,其长度可以是任意正整数。从车站 $$$u$$$ 建造一条单向铁路将花费 $$$w_u$$$ 单位资源,无论铁路终点在哪里。为了缓解拥堵,Nitori计划建成后从$$$1$$$站到任何其他车站至少有两条最短路径,并且这两条最短路径除了$$$1$$$站和航站楼外不经过同一站。此外,Nitori 也不想改变从 $$$1$$$ 站到任何其他站的最短路径的距离。
由于各种原因,有时修建新铁路的成本会不受控制地增加。此类事件总共会发生 $$$q$$$ 次,第 $$$i$$$ 次事件将为从 $$$k_i$$$ 站修建一条新铁路的成本增加 $$$x_i$$$ 的额外金额。
为了节省资源,在所有事件之前和每次事件之后,Nitori 希望你帮助她计算铁路建设的最低成本。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$、$$$1 \le m \le 3 \cdot 10^5$$$、$$$0 \le q \le 2\cdot10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^9$$$)。
接下来的 $$$m$$$ 行包含三个整数 $$$u$$$, $$$v$$$, $$$d$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$, $$$1 \le d \le 10^9$$$),表示连接车站 $$$u$$$ 和车站的双向铁路$$$v$$$,长度为$$$d$$$。
接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$k_i,x_i$$$ ($$$1 \le k_i \le n, 1 \le x_i \le 4 \times 10^8$$$)。
输出
打印$$$q+1$$$行,其中第$$$i$$$行包含一个整数,表示第$$$i-1$$$事件发生后铁路建设的最小成本(特别是第$$$0$$$事件表示没有发生事件)。
示例
输入 #1
5 5 1 1 1 1 1 1 1 2 1 2 3 1 2 4 1 3 5 1 4 5 1 1 2
输出 #1
3 9
输入 #2
8 11 0 14 4 16 15 1 3 1 14 4 2 1 1 2 3 7 5 4 2 3 1 8 6 2 8 5 5 5 4 5 7 6 7 3 5 5 1 6 6 8 1 4
输出 #2
46
输入 #3
10 16 8 29 1 75 73 51 69 24 17 1 97 1 2 18 2 3 254 2 4 546 2 5 789 5 6 998 6 7 233 7 8 433 1 9 248 5 10 488 2 6 1787 10 8 1176 3 8 2199 4 8 1907 2 10 1277 4 10 731 9 10 1047 1 11 1 9 8 8 1 3 2 19 9 5 9 4 7 6
输出 #3
34 45 54 54 57 76 96 112 112
注意
在第二个例子中,Nitori 可以建造如下铁路:$$$1 \rightarrow 2$$$、$$$1 \rightarrow 3$$$、$$$1 \rightarrow 4$$$、$$$2 \rightarrow 8$$$,成本为 $$$14 + 14 + 14 + 4 = 46$$$。