문제

JOI 나라에는 $n$개의 섬이 있으며, 각 섬에는 $1$부터 $n$까지의 번호가 붙어 있다. 현재 JOI 나라에서는 각 섬 사이를 연결하는 항로망 정비가 진행되고 있다.

당신은 선박 표를 취급하는 티켓 센터에 근무하고 있다. JOI 나라에는 선박을 이용하여 가능한 한 저렴하게 섬과 섬 사이를 여행하고 싶어 하는 사람이 많이 있으며, 그들은 출발지와 목적지를 주문표에 기입하여 당신에게 보내온다.

당신의 일은 고객으로부터 주문표를 받자마자 몇 척의 선박을 갈아타고 출발지와 목적지를 잇는 항로 중에서 가장 저렴한 운임을 계산하여 고객에게 알려주는 것이다. 단, 여정에 따라서는 선박을 이용하여 여행할 수 없는 경우도 있다. 그때는 '선박을 이용하여 여행할 수 없다'라고 고객에게 알려줄 필요가 있다. 또한 JOI 나라에서는 섬과 섬 사이를 잇는 새로운 선박이 차례차례 운항을 시작하고 있으며, 당신에게는 그 정보가 수시로 전달된다. 고객에게 답장을 할 때에는 최신 정보에 유의해야 한다.

입력으로 고객의 주문표나 새롭게 운항을 시작한 선박의 운항 정보가 주어졌을 때, 고객에 대한 답장을 구하는 프로그램을 작성하시오.

입력

입력의 $1$번째 줄에는 $2$개의 정수 $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$)가 적혀 있다. 이는 섬의 수가 $n$개이고, 입력이 $k + 1$줄로 이루어진다는 것을 나타낸다. $(i + 1)$번째 줄 ($1 \le i \le k$)에는 $3$개 또는 $4$개의 정수가 공백으로 구분되어 적혀 있다.

• 첫 번째 숫자가 $0$일 때, 이 줄은 고객의 주문표를 나타낸다. 이 줄에는 $3$개의 정수 $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$)가 공백으로 구분되어 적혀 있다. 이는 고객이 섬 $a$를 출발지로 하고 섬 $b$를 목적지로 하는 주문표를 보내왔음을 나타낸다.
• 첫 번째 숫자가 $1$일 때, 이 줄은 새롭게 운항을 시작한 선박의 운항 정보를 나타낸다. 이 줄에는 $4$개의 정수 $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$임을 나타낸다. 이 줄 이후의 주문표에 대해서는 이 선박도 고려하여 답장을 해야 한다.

처음 단계에서는 선박이 $0$척 운항하고 있는 것으로 한다. 입력 중 선박의 운항 정보를 나타내는 줄은 $1000$줄 이하이다. 또한 섬과 섬 사이에 여러 척의 선박이 운항할 수 있다는 점에 주의하라.

출력

입력 중 주문표를 나타내는 줄의 수를 $m$이라 하자. 출력은 $m$줄로 이루어지며, $i$번째 줄 ($1 \le i \le m$)에는 $i$번째 주문표에 대한 답장을 나타내는 정수를 적는다. 즉, $i$번째 주문표의 출발지와 목적지 사이를 몇 척의 선박을 갈아타고 여행하는 것이 가능하다면 그 운임 합계의 최솟값을 적는다. 여행하는 것이 불가능하다면 $-1$을 적는다.

입출력 예제

입력 예제 1

3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3

출력 예제 1

-1
15
12

입력 예제 2

5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3

출력 예제 2

5955
21431
9298
16392
24774
8840