Oppgave

I landet JOI er det $n$ øyer, og hver øy er nummerert fra $1$ til $n$. For tiden pågår utbyggingen av et rutenettverk for båter som forbinder øyene i landet JOI.

Du jobber ved et billettsenter som håndterer båtbilletter. I landet JOI er det mange som ønsker å reise mellom øyene med båt så billig som mulig; de fyller ut avreisested og destinasjon på et bestillingsskjema og sender det til deg.

Jobben din er å, straks du mottar et bestillingsskjema fra en kunde, beregne den billigste billettprisen blant rutene som forbinder avreisestedet og destinasjonen ved å bytte mellom flere båter, og informere kunden om dette. Avhengig av reiseruten kan det imidlertid hende at det ikke er mulig å reise med båt. Da må du informere kunden om at «det er umulig å reise med båt». I tillegg settes stadig nye båter som forbinder øyene i drift i landet JOI, og du får fortløpende informasjon om dette. Når du svarer kundene, må du ta hensyn til den nyeste informasjonen.

Gitt kundenes bestillingsskjemaer og driftsinformasjon om båter som nylig er satt i drift som inndata, skriv et program som finner svarene til kundene.

Inndata

På linje $1$ i inndataene står det $2$ heltall $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Dette betyr at antallet øyer er $n$, og at inndataene består av $k + 1$ linjer. På linje $(i + 1)$ ($1 \le i \le k$) står det $3$ eller $4$ heltall atskilt med mellomrom.

• Når det første tallet er $0$, representerer denne linjen et bestillingsskjema fra en kunde. På denne linjen står det $3$ heltall $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) atskilt med mellomrom. Dette betyr at en kunde har sendt inn et bestillingsskjema med øy $a$ som avreisested og øy $b$ som destinasjon.
• Når det første tallet er $1$, representerer denne linjen driftsinformasjon om en båt som nylig har startet driften. På denne linjen står det $4$ heltall $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Dette betyr at en båt som går tur-retur mellom øy $c$ og øy $d$ nylig er satt i drift, og at billettprisen med denne båten fra øy $c$ til øy $d$ og fra øy $d$ til øy $c$ begge er $e$. For bestillingsskjemaer fra og med denne linjen må du også ta denne båten i betraktning når du svarer.

I starten er det $0$ båter i drift. Blant linjene i inndataene er det høyst $1000$ linjer som representerer driftsinformasjon om båter. Merk også at flere båter kan gå mellom det samme paret av øyer.

Utdata

La $m$ være antallet linjer som representerer bestillingsskjemaer i inndataene. Utdataene består av $m$ linjer, og på linje $i$ ($1 \le i \le m$) skal du skrive et heltall som representerer svaret på det $i$-te bestillingsskjemaet. Det vil si at hvis det er mulig å reise mellom avreisestedet og destinasjonen på det $i$-te bestillingsskjemaet ved å bytte mellom flere båter, skal du skrive den minste totale billettprisen. Hvis det ikke er mulig å reise, skal du skrive $-1$.

Eksempler på inndata og utdata

Eksempel på inndata 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

Eksempel på utdata 1

-1
15
12

Eksempel på inndata 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

Eksempel på utdata 2

5955
21431
9298
16392
24774
8840