A14662. 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.

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$ ).

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).

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$ .