E. Строительство железных дорог
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поскольку железнодорожная система в Генсоке часто перегружена, инженер-энтузиастка Кавасиро Нитори планирует построить больше железных дорог, чтобы уменьшить заторы.

В Генсоке есть $$$n$$$ станций, пронумерованных от $$$1$$$ до $$$n$$$, и $$$m$$$ железных дорог с двусторонним движением. Каждая железная дорога с двусторонним движением соединяет две разные станции и имеет положительную целочисленную длину $$$d$$$. Никакие две железные дороги не соединяют одни и те же станции. Среди $$$n$$$ станций станция $$$1$$$ является главной. Вы можете добраться до любой станции от любой другой пользуясь только дорогами с двусторонним движением.

Из-за технологических ограничений Нитори может строить только односторонние железные дороги. Их длина также может быть произвольным целым положительным числом. Строительство железной дороги в один конец от станции $$$u$$$ будет стоить $$$w_u$$$ единиц ресурсов независимо от станции назначения.

Чтобы уменьшить заторы, Нитори планирует, что после строительства из станции $$$1$$$ в любую другую станцию должно быть хотя бы два различных кратчайших пути, не имеющие общих станций, кроме станции $$$1$$$ и конечной станции. Кроме того, Нитори не хочет изменять длину кратчайшего пути от станции $$$1$$$ до любой другой станции.

В силу разных причин стоимость строительства новой железной дороги иногда может расти бесконтрольно. Произойдут $$$q$$$ событий, где $$$i$$$-е событие увеличивает стоимость постройки односторонних дорог из станции $$$k_i$$$ на $$$x_i$$$.

Для экономии ресурсов Нитори хочет, чтобы вы помогли ей рассчитать минимальную стоимость строительства железной дороги до всех событий и после каждого из них.

Входные данные

Первая строка входных данных содержит три целых числа $$$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$$$.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$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$$$-е событие — ни одного события не произошло).

Примеры
Входные данные
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
Примечание

Во втором тестовом примере Нитори может строить железные дороги следующим образом: $$$1 \rightarrow 2$$$, $$$1 \rightarrow 3$$$, $$$1 \rightarrow 4$$$, $$$2 \rightarrow 8$$$. Стоимость в таком случае составит $$$14 + 14 + 14 + 4 = 46$$$.