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.

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