뱃길 여행

JOI 나라에는 $n$개의 섬이 있고, 각 섬에는 $1$부터 $n$까지의 번호가 붙어 있다. 현재 JOI 나라에서는 섬과 섬을 잇는 항로망 정비가 진행되고 있다.

당신은 배편 승선권을 취급하는 매표소에서 일하고 있다. JOI 나라에는 배를 이용해 되도록 저렴하게 섬과 섬 사이를 오가고 싶어 하는 사람이 많으며, 그들은 출발지와 목적지를 적은 주문표를 당신에게 보내온다.

당신의 일은, 손님에게서 주문표를 받는 즉시 여러 배편을 갈아타 가며 출발지와 목적지를 잇는 항로 중 가장 저렴한 운임을 계산하여 손님에게 알려 주는 것이다.

다만 여정에 따라서는 배로 이동할 수 없는 경우도 있다. 그럴 때에는 이동이 불가능하다는 뜻으로 $-1$을 답해야 한다. 또한 JOI 나라에서는 섬과 섬을 잇는 새로운 배편이 잇따라 운항을 시작하며, 그 정보가 그때그때 당신에게 전달된다. 손님에게 답할 때에는 항상 가장 최신 정보를 반영해야 한다.

손님의 주문표와 새로 운항을 시작한 배편의 정보가 입력으로 주어질 때, 각 주문표에 대한 답을 구하는 프로그램을 작성하여라.

입력의 첫째 줄에는 두 정수 $n$, $k$ ($1 \le n \le 100$, $1 \le k \le 5000$)가 주어진다. 섬의 수가 $n$개이고, 이어서 $k$개의 명령 줄이 주어진다는 뜻이다.

다음 $k$개의 줄에는 각각 정수 $3$개 또는 $4$개가 공백으로 구분되어 주어진다.

• 첫 번째 수가 $0$이면 이 줄은 손님의 주문표를 나타낸다.
  • 이 줄에는 세 정수 $0$, $a$, $b$ ($1 \le a \le n$, $1 \le b \le n$, $a \ne b$)가 주어진다.
  • 손님이 섬 $a$를 출발지로, 섬 $b$를 목적지로 하는 주문표를 보냈음을 뜻한다.
• 첫 번째 수가 $1$이면 이 줄은 새로 운항을 시작한 배편 정보를 나타낸다.
  • 이 줄에는 네 정수 $1$, $c$, $d$, $e$ ($1 \le c \le n$, $1 \le d \le n$, $c \ne d$, $1 \le e \le 1000000$)가 주어진다.
  • 섬 $c$와 섬 $d$를 왕복하는 배편이 새로 운항을 시작했으며, 섬 $c$에서 섬 $d$로 가는 운임과 섬 $d$에서 섬 $c$로 가는 운임이 모두 $e$임을 뜻한다.
  • 이 줄 이후의 주문표에 대해서는 이 배편도 고려하여 답해야 한다.

처음에는 어떤 배편도 운항하고 있지 않다. 입력에서 배편 정보를 나타내는 줄은 $1000$개 이하이다. 또한 같은 두 섬 사이에 여러 배편이 운항할 수 있음에 유의하여라.

입력에서 주문표를 나타내는 줄의 수를 $m$이라고 하자.

출력은 $m$개의 줄로 이루어지며, $i$번째 줄 ($1 \le i \le m$)에는 $i$번째 주문표에 대한 답을 정수로 출력한다.

즉, $i$번째 주문표의 출발지에서 목적지까지 여러 배편을 갈아타 이동할 수 있으면 그 운임 합의 최솟값을 출력하고, 이동이 불가능하면 $-1$을 출력한다.

아래 그림은 첫 번째 입력에서 배편이 차례로 운항을 시작하는 모습과 각 주문표에 대한 답을 그림으로 나타낸 것이다.