Railway Construction

题意翻译

**题目描述** 由于 Gensokyo 的铁路系统经常拥堵，作为一个热心的工程师， Kawasiro Nitori 计划建造更多的铁路来缓解拥堵。 在 Gensokyo 有 $n$ 个车站，编号从 $1 - n$，有 $m$ 双向铁路。 每条双向铁路都连接着两个不同的车站，并且有一个正整数的长度 $d$ 。 没有两条双向铁路连接相同的两个车站。 此外，使用这些铁路可以从任何一个车站到其他任何车站。 在这 $n$ 个车站中，$1$ 站是主要车站。你只能使用双向铁路从任何其他车站到达任何车站。 由于技术限制，NITORI 只能建造单程铁路，其长度可以是任意的正整数。 从 $u$ 站建造一条单向铁路，无论铁路的终点在哪里，都要花费 $w_u$ 单位的资源。 为了缓解拥堵，Nitori 计划在建设之后，至少有两条最短路径从车站 $1$ 到任何其他车站，而且这两条最短路径除了车站 $1$ 和终点站之外，不经过同一车站。 此外，Nitori 也不希望改变从车站 $1$ 到任何其他车站的最短路径的距离。 由于各种原因，有时建造一条新铁路的成本会不可控制地增加。 这种事件总共会有 $q$ 次，第 $i$ 次事件会给从 $ki$ 站开始的新铁路建设成本增加 $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$ 次事件意味着没有发生事件）。 Translated from [Alan_CRL](https://www.luogu.com.cn/user/349225)

题目描述

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

输入输出样例

输入样例 #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

说明

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