Road to the Olympiad

Miша solved every problem in the qualifying round and received an invitation to the on-site stage of a closed informatics olympiad. He plans to fly to the venue and wants to make at most one transfer, so he uses at most two flights. Among all such options, he wants the cheapest one.

The jury keeps the venue and date of the on-site stage secret, so Miша cannot know in advance which city he will start from. New regular flights are added from time to time, and some old ones are removed from the schedule. Write a program that answers the following queries:

1. Add a new regular flight.
2. Remove a flight.
3. Find the minimum cost of a route between two cities, considering only routes with no transfers and routes with one transfer.

Each flight connects a pair of cities $u_i$ and $v_i$ and has cost $c_i$. All flights are two-way, so they can be used in both directions.

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 100\,000$, $0 \leq m \leq 100\,000$), the number of cities and the number of flights available at the start.

Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $c_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$, $0 \leq c_i \leq 10^9$), the cities connected by the $i$-th flight and its cost.

The next line contains one integer $q$ ($1 \leq q \leq 100\,000$), the number of queries.

Each of the next $q$ lines describes a query in one of three formats:

• $1\ u_i\ v_i\ c_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$, $0 \leq c_i \leq 10^9$) adds a regular flight between cities $u_i$ and $v_i$ with cost $c_i$.
• $2\ u_i\ v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) removes the regular flight between cities $u_i$ and $v_i$. It is guaranteed that such a flight exists at the time of the query.
• $3\ u_i\ v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) asks for the cheapest way to travel from city $u_i$ to city $v_i$, using at most one transfer.

At any moment, there is at most one regular flight between any pair of cities. There is at least one query of the third type.

For each query of the third type, print the minimum cost of a trip using at most one transfer. If no suitable route exists between the given pair of cities, print $-1$.

For the sample queries of the third type, the optimal routes in input order are:

1. Through city 2. A direct flight exists, but it is not the cheapest route.
2. Through city 3.
3. Through city 2.
4. Through city 3.
5. No suitable route exists.
6. The direct flight.
7. Through city 1.
8. Through city 4.
9. No suitable route exists.