Поскольку железнодорожная система в Генсоке часто перегружена, инженер-энтузиастка Кавасиро Нитори планирует построить больше железных дорог, чтобы уменьшить заторы.
В Генсоке есть \(n\) станций, пронумерованных от \(1\) до \(n\), и \(m\) железных дорог с двусторонним движением. Каждая железная дорога с двусторонним движением соединяет две разные станции и имеет положительную целочисленную длину \(d\). Никакие две железные дороги не соединяют одни и те же станции. Среди \(n\) станций станция \(1\) является главной. Вы можете добраться до любой станции от любой другой пользуясь только дорогами с двусторонним движением.
Из-за технологических ограничений Нитори может строить только односторонние железные дороги. Их длина также может быть произвольным целым положительным числом. Строительство железной дороги в один конец от станции \(u\) будет стоить \(w_u\) единиц ресурсов независимо от станции назначения.
Чтобы уменьшить заторы, Нитори планирует, что после строительства из станции \(1\) в любую другую станцию должно быть хотя бы два различных кратчайших пути, не имеющие общих станций, кроме станции \(1\) и конечной станции. Кроме того, Нитори не хочет изменять длину кратчайшего пути от станции \(1\) до любой другой станции.
В силу разных причин стоимость строительства новой железной дороги иногда может расти бесконтрольно. Произойдут \(q\) событий, где \(i\)-е событие увеличивает стоимость постройки односторонних дорог из станции \(k_i\) на \(x_i\).
Для экономии ресурсов Нитори хочет, чтобы вы помогли ей рассчитать минимальную стоимость строительства железной дороги до всех событий и после каждого из них.
Выходные данные
Выведите \(q+1\) строк, где \(i\)-я строка содержит одно целое число, равное минимальной стоимости строительства железной дороги после \(i-1\)-го события (\(0\)-е событие — ни одного события не произошло).
Примечание
Во втором тестовом примере Нитори может строить железные дороги следующим образом: \(1 \rightarrow 2\), \(1 \rightarrow 3\), \(1 \rightarrow 4\), \(2 \rightarrow 8\). Стоимость в таком случае составит \(14 + 14 + 14 + 4 = 46\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|
|
3
|
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
|