올림피아드 가는 길

미샤는 선발 단계 문제를 모두 풀어서 비공개 정보 올림피아드의 현장 단계 초대를 받았다. 그는 항공편으로 대회장에 가려고 하며, 환승은 최대 한 번까지만 하고 싶다. 즉 이용하는 항공편은 최대 두 편이다. 이런 경로 중에서 가장 저렴한 것을 찾고 싶어 한다.

심사위원회는 현장 단계의 장소와 날짜를 철저히 비밀로 한다. 그래서 미샤는 어느 도시에서 출발할지 미리 알 수 없다. 또한 새로운 정기편이 생기기도 하고, 기존 정기편이 시간표에서 빠지기도 한다. 미샤를 위해 다음 질의에 답하는 프로그램을 작성하라.

1. 새로운 정기편을 추가한다.
2. 정기편 하나를 삭제한다.
3. 두 도시 사이의 최소 비용을 구한다. 환승이 없는 경로와 환승이 한 번 있는 경로만 고려한다.

각 정기편은 도시 $u_i$와 $v_i$를 잇고, 비용은 $c_i$이다. 모든 정기편은 양방향이어서 어느 방향으로든 이용할 수 있다.

첫 줄에 정수 $n$과 $m$ ($2 \leq n \leq 100\,000$, $0 \leq m \leq 100\,000$)이 주어진다. 각각 도시의 수와 처음에 이용 가능한 정기편의 수이다.

이어지는 $m$개의 줄에는 정수 $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$)가 주어진다. $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 \leq c_i \leq 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$ 사이의 정기편을 취소한다는 뜻이다. 이 질의가 들어오는 시점에 두 도시가 정기편으로 연결되어 있음이 보장된다.
• $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. 적절한 경로가 없다.