題目描述

在 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