Problem

I landet JOI finns det $n$ öar, och varje ö är numrerad från $1$ till $n$. För närvarande pågår utbyggnaden av ett linjenät för båtar som förbinder öarna i landet JOI.

Du arbetar på ett biljettcenter som hanterar båtbiljetter. I landet JOI finns det många människor som vill resa mellan öarna med båt så billigt som möjligt; de fyller i avreseort och destination på en beställningsblankett och skickar den till dig.

Ditt arbete är att, så snart du får en beställningsblankett från en kund, beräkna det billigaste biljettpriset bland de rutter som förbinder avreseorten och destinationen genom att byta mellan flera båtar, och meddela kunden detta. Beroende på resplanen kan det dock hända att det inte går att resa med båt. I så fall måste du meddela kunden att "det går inte att resa med båt". Dessutom tas nya båtar som förbinder öarna i bruk efter hand i landet JOI, och du får fortlöpande information om detta. När du svarar kunderna måste du ta hänsyn till den senaste informationen.

Givet kundernas beställningsblanketter och trafikinformation om båtar som nyligen tagits i bruk som indata, skriv ett program som beräknar svaren till kunderna.

Indata

På rad $1$ i indatan står $2$ heltal $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Detta anger att antalet öar är $n$ och att indatan består av $k + 1$ rader. På rad $(i + 1)$ ($1 \le i \le k$) står $3$ eller $4$ heltal separerade med blanksteg.

• När det första talet är $0$ representerar denna rad en kunds beställningsblankett. På denna rad står $3$ heltal $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) separerade med blanksteg. Detta betyder att en kund har skickat in en beställningsblankett med ö $a$ som avreseort och ö $b$ som destination.
• När det första talet är $1$ representerar denna rad trafikinformation om en båt som nyligen tagits i bruk. På denna rad står $4$ heltal $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Detta betyder att en båt som går tur och retur mellan ö $c$ och ö $d$ nyligen har tagits i bruk, och att biljettpriset med denna båt från ö $c$ till ö $d$ samt från ö $d$ till ö $c$ båda är $e$. För beställningsblanketter från och med denna rad måste du även ta hänsyn till denna båt när du svarar.

I utgångsläget är $0$ båtar i trafik. I indatan är antalet rader som representerar trafikinformation om båtar högst $1000$. Observera också att flera båtar kan trafikera sträckan mellan samma par av öar.

Utdata

Låt $m$ vara antalet rader som representerar beställningsblanketter i indatan. Utdatan består av $m$ rader, och på rad $i$ ($1 \le i \le m$) ska ett heltal skrivas som representerar svaret på den $i$-te beställningsblanketten. Det vill säga, om det är möjligt att resa mellan avreseorten och destinationen på den $i$-te beställningsblanketten genom att byta mellan flera båtar, skriv ut den minsta totala biljettkostnaden. Om det är omöjligt att resa, skriv ut $-1$.

Exempel på indata och utdata

Indataexempel 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

Utdataexempel 1

-1
15
12

Indataexempel 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

Utdataexempel 2

5955
21431
9298
16392
24774
8840