Verkefni

Í JOI-landi eru $n$ eyjar og er hver eyja númeruð frá $1$ til $n$. Nú stendur yfir uppbygging á siglingakerfi sem tengir saman eyjarnar í JOI-landi.

Þú vinnur á miðasölu sem sér um bátsmiða. Í JOI-landi eru margir sem vilja ferðast á milli eyja með báti eins ódýrt og hægt er; þeir skrá brottfararstað og áfangastað á pöntunarblað og senda til þín.

Starf þitt er að reikna út ódýrasta fargjaldið á milli brottfararstaðar og áfangastaðar með því að skipta á milli nokkurra báta um leið og þú færð pöntunarblað frá viðskiptavini, og láta viðskiptavininn vita. Hins vegar getur verið ómögulegt að ferðast með báti, allt eftir ferðaáætluninni. Þá þarf að láta viðskiptavininn vita að „ekki er hægt að ferðast með báti“. Að auki eru nýir bátar sem tengja eyjarnar sífellt að hefja siglingar í JOI-landi og berast þér upplýsingar um það jafnóðum. Þegar þú svarar viðskiptavinum verður þú að hafa nýjustu upplýsingar í huga.

Þegar pöntunarblöð viðskiptavina og upplýsingar um báta sem nýlega hafa hafið siglingar eru gefnar sem inntak, skrifið forrit sem finnur svörin til viðskiptavinanna.

Inntak

Á línu $1$ í inntakinu eru $2$ heiltölur $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Þetta gefur til kynna að fjöldi eyja sé $n$ og að inntakið samanstandi af $k + 1$ línum. Á línu $(i + 1)$ ($1 \le i \le k$) eru $3$ eða $4$ heiltölur aðskildar með bilum.

• Þegar fyrsta talan er $0$ táknar þessi lína pöntunarblað frá viðskiptavini. Á þessari línu eru $3$ heiltölur $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) aðskildar með bilum. Þetta þýðir að viðskiptavinur hefur sent pöntunarblað þar sem eyja $a$ er brottfararstaður og eyja $b$ er áfangastaður.
• Þegar fyrsta talan er $1$ táknar þessi lína upplýsingar um bát sem nýlega hefur hafið siglingar. Á þessari línu eru $4$ heiltölur $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Þetta þýðir að bátur sem siglir fram og til baka milli eyju $c$ og eyju $d$ hefur nýlega hafið siglingar og að fargjaldið með þessum báti frá eyju $c$ til eyju $d$ og frá eyju $d$ til eyju $c$ sé hvoru tveggja $e$. Fyrir pöntunarblöð frá og með þessari línu verður að svara með tilliti til þessa báts líka.

Í upphafi eru $0$ bátar í siglingum. Í inntakinu eru í mesta lagi $1000$ línur sem tákna upplýsingar um siglingar báta. Athugið einnig að fleiri en einn bátur geta siglt á milli sömu tveggja eyjanna.

Úttak

Látum $m$ vera fjölda lína í inntakinu sem tákna pöntunarblöð. Úttakið samanstendur af $m$ línum og á línu $i$ ($1 \le i \le m$) á að skrifa heiltölu sem táknar svarið við $i$-ta pöntunarblaðinu. Það er, ef hægt er að ferðast á milli brottfararstaðar og áfangastaðar á $i$-ta pöntunarblaðinu með því að skipta á milli nokkurra báta, skrifið þá lágmarkssummu fargjaldanna. Ef ómögulegt er að ferðast, skrifið $-1$.

Dæmi um inntak og úttak

Inntaksdæmi 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

Úttaksdæmi 1

-1
15
12

Inntaksdæmi 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

Úttaksdæmi 2

5955
21431
9298
16392
24774
8840