CF1580E.Railway Construction

Because the railway system in Gensokyo is often congested, as an enthusiastic engineer, Kawasiro Nitori plans to construct more railway to ease the congestion.

There are $n$ stations numbered from $1$ to $n$ and $m$ two-way railways in Gensokyo. Every two-way railway connects two different stations and has a positive integer length $d$. No two two-way railways connect the same two stations. Besides, it is possible to travel from any station to any other using those railways. Among these $n$ stations, station $1$ is the main station. You can get to any station from any other station using only two-way railways.

Because of the technological limitation, Nitori can only construct one-way railways, whose length can be arbitrary positive integer. Constructing a one-way railway from station $u$ will costs $w_u$ units of resources, no matter where the railway ends. To ease the congestion, Nitori plans that after construction there are at least two shortest paths from station $1$ to any other station, and these two shortest paths do not pass the same station except station $1$ and the terminal. Besides, Nitori also does not want to change the distance of the shortest path from station $1$ to any other station.

Due to various reasons, sometimes the cost of building a new railway will increase uncontrollably. There will be a total of $q$ occurrences of this kind of incident, and the $i$-th event will add additional amount of $x_i$ to the cost of building a new railway from the station $k_i$.

To save resources, before all incidents and after each incident, Nitori wants you to help her calculate the minimal cost of railway construction.

由于幻想乡的铁路系统经常拥堵，作为一位热心的工程师，河城荷取计划修建更多的铁路以缓解拥堵。

幻想乡共有 $n$ 个车站，编号从 $1$ 到 $n$，以及 $m$ 条双向铁路。每条双向铁路连接两个不同的车站，且具有一个正整数长度 $d$。任意两条双向铁路不会连接完全相同的两个车站。此外，仅通过这些双向铁路，任意两个车站之间均可互相到达。在这 $n$ 个车站中，车站 $1$ 是主车站——即从任意车站出发，均可仅通过双向铁路抵达其余任意车站。

受限于技术条件，荷取只能修建单向铁路，其长度可为任意正整数。从车站 $u$ 出发修建一条单向铁路的花费为 $w_u$ 单位资源，与该铁路的终点无关。为缓解拥堵，荷取计划：在新建铁路完成后，对于任意其他车站 $v$，从车站 $1$ 到 $v$ 至少存在两条最短路径，且这两条最短路径除起点 $1$ 和终点 $v$ 外，不经过任何相同车站。此外，荷取也不希望改变从车站 $1$ 到任意其他车站的最短路径长度。

由于种种原因，有时新建铁路的建造成本会失控地上涨。此类事件总共会发生 $q$ 次，其中第 $i$ 次事件会使从车站 $k_i$ 出发修建新铁路的成本额外增加 $x_i$。

为节约资源，在所有事件发生前，以及每次事件发生后，荷取希望你帮她计算铁路建设的最小总成本。

The first line contains three integers $n$, $m$, and $q$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 3 \cdot 10^5$, $0 \le q \le 2\cdot10^5$).

The second line contains $n$ integers $w_1,w_2,\ldots,w_n$ ($1 \le w_i \le 10^9$).

Each of the next $m$ lines contains three integers $u$, $v$, $d$ ($1 \le u,v \le n$, $u \ne v$, $1 \le d \le 10^9$), denoting a two-way railway connecting station $u$ and station $v$, with length $d$.

The $i$-th of the next $q$ lines contains two integers $k_i,x_i$ ($1 \le k_i \le n, 1 \le x_i \le 4 \times 10^8$).

第一行包含三个整数 $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$）。

Print $q+1$ lines, and the $i$-th of these lines contains one integer, denoting the minimal cost of railway construction after the $i-1$-th incident (especially, the $0$-th incident means no incident occurred).

输出 $q+1$ 行，其中第 $i$ 行包含一个整数，表示在第 $i-1$ 次事故（特别地，第 $0$ 次事故表示未发生任何事故）之后铁路建设的最小代价。

In the second example, Nitori can build railways as follows: $1 \rightarrow 2$, $1 \rightarrow 3$, $1 \rightarrow 4$, $2 \rightarrow 8$, and the cost is $14 + 14 + 14 + 4 = 46$.

在第二个例子中，Nitori 可以按如下方式修建铁路：$1 \rightarrow 2$、$1 \rightarrow 3$、$1 \rightarrow 4$、$2 \rightarrow 8$，总花费为 $14 + 14 + 14 + 4 = 46$。