Railway Construction

2000ms

524288K

Description:

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.

Input:

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

Output:

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

Sample Input:

Sample Output:

3
9

Sample Input:

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

Sample Output:

Sample Input:

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

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF1580E