A90630.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$ 次事件意味着没有发生事件）。