第一行三个正整数 $$$n,m,q$$$ $$$(1\le n,q\le 5\times 10^5; n-1\le m \le \min\{\frac{n(n+1)}{2},5\times 10^5\})$$$，分别表示城市的数量，线路的数量，询问的次数。

第二行 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n$$$ $$$(1\le a_i \le 10^9)$$$，表示每个城市的繁荣程度。

接下来 $$$m$$$ 行，每行三个正整数 $$$x_i,y_i,d_i$$$ $$$(1\le x_i,y_i\le n; x_i \neq y_i; 1\le d_i \le 10^9)$$$，分别表示第 $$$i$$$ 条线路连接的两个城市的编号，以及该线路修建的难度系数。保证图联通，无重边自环。

接下来 $$$q$$$ 行，每行先输入一个正整数 $$$op_i$$$ $$$(1\le op_i\le 2)$$$。

如果 $$$op_i=1$$$，则接下来输入两个正整数 $$$c_i,t_i$$$ $$$(1\le c_i\le n;1\le t_i\le 10^9)$$$，表示编号为 $$$c_i$$$ 的城市繁荣程度变为了 $$$t_i$$$；

如果 $$$op_i=2$$$，则接下来输入一个正整数 $$$k_i$$$ $$$(1\le k_i\le n)$$$，询问当前局面下选择最繁荣的 $$$k_i$$$ 个城市举办比赛，至少需要花费多少经费。（如果两个城市的繁荣程度相同，则优先选择编号较小的城市）。