Задача . G. Кратчайшие пути

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 200000) — количество вершин и количество ребер в графе соответственно.

Затем следуют m строк, описывающие ребра графа. В каждой строке записаны три целых числа x, y и d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 2³⁰ - 1). Каждая пара (x, y) встречается не более одного раза. Изначально граф связный.

В следующей строке записано одно целое число q (1 ≤ q ≤ 200000) — количество запросов.

Затем следуют q строк, описывающие запросы следующим образом:

• 1 x y d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 2³⁰ - 1) — добавить ребро, соединяющее вершины x и y с весом d. Гарантируется, что до запроса не было ребра, соединяющего x и y;
• 2 x y (1 ≤ x < y ≤ n) — удалить ребро, соединяющее вершины x и y. Гарантируется, что в графе есть такое ребро и что граф останется связным после запроса;
• 3 x y (1 ≤ x < y ≤ n) — найти длину кратчайшего пути (не обязательно простого) от вершины x в вершину y.

Гарантируется, что существует хотя бы один запрос типа 3.