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