G. Четыре вершины
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный взвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер.

На этом графе осуществляются запросы:

  • Удалить из графа существующее ребро.
  • Добавить в граф ещё не существующее в нём ребро.

В самом начале и после каждого запроса вам необходимо найти четыре различные вершины $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ такие, что существует путь между $$$a$$$ и $$$b$$$, существует путь между $$$c$$$ и $$$d$$$ и сумма длин двух кратчайших путей из $$$a$$$ в $$$b$$$ и из $$$c$$$ в $$$d$$$ минимальна. Ответ на запрос — это сумма длин этих двух кратчайших путей. Длина пути равна сумме весов рёбер на этом пути.

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

В первой строке находится два целых числа $$$n$$$ и $$$m$$$ $$$(4 \le n, m \le 10^5)$$$ — количество вершин и рёбер в графе соответственно.

Каждая из следующих $$$m$$$ строк содержит три целых числа $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$) — это означает, что существует ребро между вершинами $$$v$$$ и $$$u$$$ с весом $$$w$$$.

Следующая строка содержит одно целое число $$$q$$$ $$$(0 \le q \le 10^5)$$$ — количество запросов.

Следующие $$$q$$$ строк содержат запросы двух типов:

  • $$$0$$$ $$$v$$$ $$$u$$$ — такой запрос означает удаление ребра между вершинами $$$v$$$ и $$$u$$$ $$$(1 \le v, u \le n, v \neq u)$$$. Гарантируется, что такое ребро существует в графе.
  • $$$1$$$ $$$v$$$ $$$u$$$ $$$w$$$ — такой запрос означает добавление ребра между вершинами $$$v$$$ и $$$u$$$ весом $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$). Гарантируется, что такого ребра не было в графе.

Гарантируется, что изначальный граф не содержит кратных рёбер.

В самом начале и после каждого запроса граф не обязательно связный.

Гарантируется, что в любой момент количество рёбер в графе не будет меньше $$$4$$$. Можно доказать, что в любой момент существуют четыре различные вершины $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ такие, что существует путь между вершинами $$$a$$$ и $$$b$$$, и существует путь между вершинами $$$c$$$ и $$$d$$$.

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

Выведите $$$q + 1$$$ целое число — минимальную сумму длин кратчайших путей для выбранных пар вершин до всех запросов и после каждого из них.

Пример
Входные данные
6 6
1 3 6
4 3 1
1 4 1
2 6 4
2 4 2
5 4 3
4
1 2 5 2
0 1 4
0 3 4
1 6 1 3
Выходные данные
4
3
3
7
5
Примечание

До всех запросов можно выбрать вершины $$$(a, b) = (3, 2)$$$ и $$$(c, d) = (1, 4)$$$. Сумма длин двух кратчайших путей равна $$$3 + 1 = 4$$$.

После первого запроса можно выбрать вершины $$$(a, b) = (2, 5)$$$ и $$$(c, d) = (1, 4)$$$. Сумма длин двух кратчайших путей равна $$$2 + 1 = 3$$$.

После второго запроса можно выбрать вершины $$$(a, b) = (3, 4)$$$ и $$$(c, d) = (2, 5)$$$. Сумма длин двух кратчайших путей равна $$$1 + 2 = 3$$$.

После третьего запроса можно выбрать вершины $$$(a, b) = (2, 6)$$$ и $$$(c, d) = (4, 5)$$$. Сумма длин двух кратчайших путей равна $$$4 + 3 = 7$$$.

После последнего запроса можно выбрать вершины $$$(a, b) = (1, 6)$$$ и $$$(c, d) = (2, 5)$$$. Сумма длин двух кратчайших путей равна $$$3 + 2 = 5$$$.