H. Стандартная задача на графы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан взвешенный ориентированный граф, содержащий $$$n$$$ вершин и $$$m$$$ ребер. Каждая вершина графа может быть выделенной или обычной, изначально все вершины обычные. Ценой графа назовём минимальную суммарную цену рёбер, которые нужно взять, чтобы из каждой обычной вершины была достижима по взятым ребрам хотя бы одна любая выделенная вершина. Если такого набора рёбер не существует, то цена равна $$$-1$$$.

Вам предстоит вычислить цену графа после каждого из $$$q$$$ запросов. Запросы бывают двух типов:

  • $$$+\;v_i$$$ делает вершину $$$v_i$$$ выделенной; гарантируется, что перед запросом вершина была обычной.
  • $$$-\;v_i$$$ делает вершину $$$v_i$$$ обычной; гарантируется, что перед запросом вершина была выделенной.

Выведите цену графа после каждого из $$$q$$$ запросов.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5$$$) — количество вершин графа, количество рёбер и число запросов.

Следующие $$$m$$$ строк содержат рёбра графа, по одному ребру в каждой строке. $$$i$$$-я строка содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$c_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6$$$) — концы $$$i$$$-го ребра (из $$$u_i$$$ в $$$v_i$$$), а также его вес ($$$c_i$$$).

Следующие $$$q$$$ строк содержат запросы, по одному запросу в каждой строке. $$$i$$$-я строка содержит $$$+\;v_i$$$, если это операция первого типа, и $$$-\;v_i$$$, если это операция второго типа ($$$1 \leq v_i \leq n$$$).

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

Выведите $$$q$$$ чисел. $$$i$$$-е число — это цена графа после первых $$$i$$$ запросов.

Примеры
Входные данные
4 5 6
1 2 1
2 3 5
3 2 3
4 1 8
2 1 4
+ 1
- 1
+ 3
+ 1
+ 4
+ 2
Выходные данные
15
-1
14
12
4
0
Входные данные
10 14 10
8 6 4
2 5 1
3 5 4
1 6 3
1 3 7
7 2 1
6 1 3
4 10 1
4 6 5
5 4 1
5 8 10
10 9 1
9 5 1
9 7 6
+ 7
+ 8
- 7
+ 10
+ 2
- 10
+ 5
- 2
- 5
+ 3
Выходные данные
28
24
29
19
18
24
18
19
29
20
Примечание

В первом тесте:

  • Посыле первого запроса выгоднее всего взять ребра с номерами $$$3, 4, 5$$$, сумма их цен равна $$$15$$$.
  • После второго запроса, нет ни одной выделенной вершины, а значит, не существует подходящих наборов ребер, цена графа $$$-1$$$.
  • После третьего запроса выгоднее всего взять ребра с номерами $$$1, 2, 5$$$, сумма их цен равна $$$14$$$.
  • После четвертого запроса выгоднее всего взять ребра с номерами $$$4$$$ и $$$5$$$, сумма их цен равна $$$12$$$.
  • После пятого запроса выгоднее всего взять только ребро номер $$$5$$$, его цена равна $$$4$$$.
  • После шестого запроса все вершины выделенные и можно не брать ребер, цена графа равна $$$0$$$.