Tehtävä

JOI-maassa on $n$ saarta, ja jokainen saari on numeroitu luvuin $1$:stä $n$:ään. Tällä hetkellä JOI-maassa kehitetään saarten välistä laivareittiverkostoa.

Työskentelet laivalippuja välittävässä lippupalvelussa. JOI-maassa on paljon ihmisiä, jotka haluavat matkustaa saarten välillä laivalla mahdollisimman edullisesti; he täyttävät lähtöpaikan ja määränpään tilauslomakkeeseen ja lähettävät sen sinulle.

Tehtäväsi on heti asiakkaan tilauslomakkeen saatuasi laskea halvin matkahinta niiden reittien joukosta, jotka yhdistävät lähtöpaikan ja määränpään vaihtamalla tarvittaessa laivasta toiseen, ja ilmoittaa se asiakkaalle. Reitistä riippuen voi kuitenkin olla, ettei matkustaminen laivalla ole mahdollista. Silloin asiakkaalle on ilmoitettava, että "matkustaminen laivalla ei ole mahdollista". Lisäksi JOI-maassa aloittaa jatkuvasti liikennöinnin uusia saaria yhdistäviä laivoja, ja saat tästä tiedon aina tuoreeltaan. Asiakkaille vastatessasi sinun on otettava huomioon viimeisimmät tiedot.

Kun syötteenä annetaan asiakkaiden tilauslomakkeet sekä liikennöinnin aloittavien uusien laivojen liikennetiedot, kirjoita ohjelma, joka selvittää asiakkaille annettavat vastaukset.

Syöte

Syötteen rivillä $1$ on $2$ kokonaislukua $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Tämä tarkoittaa, että saaria on $n$ kappaletta ja syöte koostuu $k + 1$ rivistä. Rivillä $(i + 1)$ ($1 \le i \le k$) on $3$ tai $4$ kokonaislukua välilyönnein erotettuina.

• Kun ensimmäinen luku on $0$, tämä rivi kuvaa asiakkaan tilauslomaketta. Tällä rivillä on välilyönnein erotettuina $3$ kokonaislukua $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$). Tämä tarkoittaa, että asiakas on lähettänyt tilauslomakkeen, jossa lähtöpaikkana on saari $a$ ja määränpäänä saari $b$.
• Kun ensimmäinen luku on $1$, tämä rivi kuvaa uuden liikennöinnin aloittaneen laivan tietoja. Tällä rivillä on $4$ kokonaislukua $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Tämä tarkoittaa, että saaren $c$ ja saaren $d$ välillä edestakaisin kulkeva laiva on aloittanut liikennöinnin, ja tämän laivan matkahinta sekä saarelta $c$ saarelle $d$ että saarelta $d$ saarelle $c$ on $e$. Tämän rivin jälkeisiin tilauslomakkeisiin vastattaessa on otettava huomioon myös tämä laiva.

Alkuvaiheessa liikennöiviä laivoja on $0$. Syötteessä laivojen liikennetietoja kuvaavia rivejä on enintään $1000$. Huomaa myös, että kahden saaren välillä voi liikennöidä useita laivoja.

Tuloste

Olkoon tilauslomakkeita kuvaavien rivien lukumäärä syötteessä $m$. Tuloste koostuu $m$ rivistä, ja riville $i$ ($1 \le i \le m$) kirjoitetaan kokonaisluku, joka ilmaisee vastauksen $i$:nteen tilauslomakkeeseen. Toisin sanoen, jos $i$:nnen tilauslomakkeen lähtöpaikan ja määränpään välillä on mahdollista matkustaa vaihtamalla laivasta toiseen, tulosta matkahintojen summan pienin arvo. Jos matkustaminen on mahdotonta, tulosta $-1$.

Syöte- ja tulosteesimerkit

Syöteesimerkki 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

Tulosteesimerkki 1

-1
15
12

Syöteesimerkki 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

Tulosteesimerkki 2

5955
21431
9298
16392
24774
8840