Migrated from Lutece 3258 罗门帝国特聘道路建造师

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

罗门帝国有 $n$ 座城市，被编号为 $1 \sim n$，其中城市 $1$ 为国都；$m$ 条双向道路，每条双向道路连接两个不同的城市，每条道路都拥有一个长度 $d_i$。没有两条道路连接相同的两座城市，并且从任意一座城市能通过这些道路到达其他任意一座城市。

现在，lllei 被聘请为罗门帝国的道路建造师，他只能修建单向道路，道路长度可以是任意一个正整数。从城市 $u$ 开始修建的道路，无论终点在哪，都需要花费 $w_u$。

国王对他提出了以下要求：

1. 你可以修建任意条道路（单向道路）；
2. 每条道路的长度可以各不相同（但都需要是正整数）；
3. 修建道路后，从国都（即城市 $1$）到达其他任意城市的最短路长度不变；
4. 从国都到其他任意城市至少有两条不同最短路径，不同的最短路径是指除起点和终点，经过的城市和道路都不能有交集。

但随时间流逝，罗门帝国的物价也在上涨，具体而言：有 $q$ 个时间点，每个时间点后，$w_{k_i}$ 会增加 $x_i$。

现在，lllei 向你求助，询问在第一个时间点之前，以及在每个时间点后建设出满足国王要求的道路的最小代价。

Input

第一行三个整数 $n, m, q$。

接下来一行包含 $n$ 个正整数，第 $i$ 个整数代表 $w_i$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, d_i$，代表第 $i$ 条双向道路的两个端点以及道路长度。

接下来 $q$ 行，每行两个整数 $k_i, x_i$（注意每个时间点对 $w_{k_i}$ 的修改是永久的）。

Output

一共 $q + 1$ 行，第一行代表第一个时间点之前的最小代价，接下来 $q$ 行依次代表每个时间点之后的最小代价。

Samples

5 5 1
1 1 1 1 1
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1
1 2

3
9

8 11 0
14 4 16 15 1 3 1 14
4 2 1
1 2 3
7 5 4
2 3 1
8 6 2
8 5 5
5 4 5
7 6 7
3 5 5
1 6 6
8 1 4

46

10 16 8
29 1 75 73 51 69 24 17 1 97
1 2 18
2 3 254
2 4 546
2 5 789
5 6 998
6 7 233
7 8 433
1 9 248
5 10 488
2 6 1787
10 8 1176
3 8 2199
4 8 1907
2 10 1277
4 10 731
9 10 1047
1 11
1 9
8 8
1 3
2 19
9 5
9 4
7 6

34
45
54
54
57
76
96
112
112

Constraints

$1 \le n \le 2 \times 10^5$

$n - 1 \le m \le 3 \times 10^5$

$0 \le q \le 2 \times 10^5$

$1 \le w_i \le 10^9$

$1 \le u_i, v_i \le n, u_i \neq v_i$

$1 \le d_i \le 10^9$

$1 \le k_i \le n$

$1 \le x_i \le 10^8$

Note

在第二组样例中，lllei 可以修建道路 $1 \rarr 2$，$1 \rarr 3$，$2 \rarr 8$，最后花费为 $14 + 14 + 14 + 4 = 46$。