題目描述

喺 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