30735번 - Дорога на олимпиаду 다국어

문제

Успешно решив все задачи отборочного этапа, Миша получил приглашение принять участие в очном туре Закрытой олимпиады школьников по информатике. Миша планирует добираться до места проведения олимпиады самолётами, при этом он хочет совершить не более одной пересадки, то есть использовать не более двух рейсов. Разумеется, среди всех таких вариантов его интересует самый дешёвый.

Жюри Закрытой олимпиады держит место и дату проведения очного этапа олимпиады в строжайшем секрете, а Миша очень любит путешествовать, поэтому не может заранее знать, из какого города он будет начинать свой путь. Кроме того, периодически появляются новые регулярные рейсы, а некоторые старые наоборот исчезают из расписания, поэтому Миша просит вас написать программу, которая будет отвечать на следующие запросы:

1. Добавить новый регулярный рейс.
2. Удалить некоторый рейс.
3. Определить минимальную стоимость маршрута между двумя городами, если рассматривать только маршруты без пересадок и маршруты с одной пересадкой.

Каждый рейс связывает некоторую пару городов $u_i$ и $v_i,ドル и имеет свою стоимость $c_i$. Все рейсы двусторонние, то есть позволяют добраться как из города $u_i$ в город $v_i,ドル так и наоборот, из города $v_i$ в город $u_i$.

입력

В первой строке входных данных записаны два целых числа $n$ и $m$ (2ドル \leq n \leq 100,000円,ドル 0ドル \leq m \leq 100,000円$) --- количество городов и количество уже доступных рейсов соответственно.

Следующие $m$ строк описывают имеющиеся рейсы. В $i$-й из этих строк записаны три целых числа $u_i,ドル $v_i$ и $c_i$ (1ドル \leq u_i, v_i \leq n,ドル $u_i \ne v_i,ドル 0ドル \le c_i \le 10^9$) --- номера городов, которые связывает $i$-й регулярный рейс, и его стоимость.

В следующей строке записано одно целое число $q$ (1ドル \leq q \leq 100,000円$) --- количество запросов.

Каждая из последующих $q$ строк содержит описание запроса в одном из трёх форматов:

• 1ドル,円 u_i,円 v_i,円 c_i$ (1ドル \leq u_i, v_i \leq n,ドル $u_i \ne v_i,ドル 0ドル \le c_i \le 10^9$) соответствует добавлению регулярного рейса между городами $u_i$ и $v_i$ стоимостью $c_i$.
• 2ドル,円 u_i,円 v_i$ (1ドル \leq u_i, v_i \leq n,ドル $u_i \ne v_i$) соответствует отмене регулярного рейса между городами $u_i$ и $v_i$. Гарантируется, что в момент поступления такого запроса, города $u_i$ и $v_i$ соединены регулярным рейсом.
• 3ドル,円 u_i,円 v_i$ (1ドル \leq u_i, v_i \leq n,ドル $u_i \ne v_i$) означает, что Миша хочет знать самый дешёвый способ добраться из города $u_i$ в город $v_i,ドル при условии использования не более, чем одной пересадки.

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

출력

Для каждого запроса третьего типа выведите минимальную стоимость поездки с использованием не более одной пересадки. Если между указанной парой городов вовсе не существует подходящих маршрутов, то выведите $-1$.

제한

노트

Рассмотрим пример. Для запросов третьего типа перечислим оптимальные маршруты в порядке появления этих запросов во входных данных:

1. Через город 2ドル$ (хотя существует и прямой рейс, он не является наиболее выгодным маршрутом).
2. Через город 3ドル$.
3. Через город 2ドル$.
4. Через город 3ドル$.
5. Подходящего маршрута не существует.
6. Прямой рейс.
7. Через город 1ドル$.
8. Через город 4ドル$.
9. Подходящего маршрута не существует.