B'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 <= n <= 2 cdot 10^5 , 1 <= m <= 3 cdot 10^5 , 0 <= q <= 2 cdot10^5 ). The second line contains n integers w_1,w_2, ldots,w_n ( 1 <= w_i <= 10^9 ). Each of the ne'...