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

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

Idx	Name	Rating
A	Portal	1700
B	Mathematics Curriculum	2600
C	Train Maintenance	2200
D	Subsequence	2900
E	Railway Construction	3400
F	Problems for Codeforces	3300

Codeforces Round 745 (Div. 1)