该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

A 国要举办世界杯了!

为了迎接世界杯的到来，A 国打算修建高铁连接所有举办城市。（A国目前还没有修建高铁）

A 国有 $n$ 个城市，$m$ 条线路有条件修建高铁，每条线路有各自的修建难度系数。

为了更好地施工，A 国打算进口一台高级设备。但由于经费紧张，只能进口一台。如果进口了一台价格为 $V$ 的设备，那么该设备可以修所有难度系数不超过 $V$ 的路线。

此外，每个城市有一个繁荣程度。为了展现国家实力，A 国肯定要在最繁荣的几个城市举办比赛。但随着时间的推移，每个城市的繁荣程度也在不断发生变化。

作为 A 国元首，你想知道，在当前局面下，若选择最繁荣的 $k$ 个城市举办比赛，想用高铁连接这些城市，至少需要花费多少经费（购买设备）。

输入格式

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

第二行 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n} (1 \leq a_{i} \leq 10^{9})$ ，表示每个城市的繁荣程度。

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

接下来 $q$ 行，每行先输入一个正整数 $op_{i}$ $(1\leq op_{i}\leq 2)$ 。

• 如果 $op_{i} = 1$ ，则接下来输入两个正整数 $c_{i}, t_{i} (1 \leq c_{i} \leq n; 1 \leq t_{i} \leq 10^{9})$ ，表示编号为 $c_{i}$ 的城市繁荣程度变为了 $t_{i}$ ；
• 如果 $op_{i} = 2$ ，则接下来输入一个正整数 $k_{i}$ $(1\leq k_{i}\leq n)$ ，询问当前局面下选择最繁荣的 $k_{i}$ 个城市举办比赛，至少需要花费多少经费。（如果两个城市的繁荣程度相同，则优先选择编号较小的城市）。

输出格式

对于每个询问，输出一行一个正整数表示答案。

4 4 8
4 3 2 1
1 2 4
3 2 1
3 4 2
4 1 3
2 2
1 3 4
1 4 4
2 2
1 3 5
1 4 6
2 2
2 1

3
3
2
0