Problema

Nel paese di JOI ci sono $n$ isole, ciascuna numerata da $1$ a $n$. Attualmente, nel paese di JOI è in corso lo sviluppo di una rete di rotte navali che collegano le varie isole.

Lavori in una biglietteria che si occupa di biglietti navali. Nel paese di JOI ci sono molte persone che desiderano viaggiare tra le isole in nave spendendo il meno possibile; esse compilano un modulo d'ordine indicando il luogo di partenza e la destinazione e te lo inviano.

Il tuo compito è, non appena ricevi un modulo d'ordine da un cliente, calcolare la tariffa più economica tra le rotte che collegano la partenza e la destinazione effettuando trasbordi tra più navi, e comunicarla al cliente. Tuttavia, a seconda dell'itinerario, potrebbe non essere possibile viaggiare in nave. In tal caso, è necessario comunicare al cliente che «non è possibile viaggiare in nave». Inoltre, nel paese di JOI nuove navi che collegano le isole entrano in servizio una dopo l'altra, e queste informazioni ti vengono comunicate di volta in volta. Quando rispondi ai clienti, devi tenere conto delle informazioni più aggiornate.

Dati in input i moduli d'ordine dei clienti e le informazioni sulle navi appena entrate in servizio, scrivi un programma che determini le risposte da dare ai clienti.

Input

Nella riga $1$ dell'input sono scritti $2$ interi $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Ciò indica che il numero di isole è $n$ e che l'input è composto da $k + 1$ righe. Nella riga $(i + 1)$ ($1 \le i \le k$) sono scritti $3$ oppure $4$ interi separati da spazi.

• Quando il primo numero è $0$, questa riga rappresenta il modulo d'ordine di un cliente. In questa riga sono scritti $3$ interi $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) separati da spazi. Ciò significa che un cliente ha inviato un modulo d'ordine con l'isola $a$ come partenza e l'isola $b$ come destinazione.
• Quando il primo numero è $1$, questa riga rappresenta le informazioni di servizio di una nave appena entrata in funzione. In questa riga sono scritti $4$ interi $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Ciò significa che una nave che fa la spola tra l'isola $c$ e l'isola $d$ ha appena iniziato il servizio, e che la tariffa di questa nave dall'isola $c$ all'isola $d$ e quella dall'isola $d$ all'isola $c$ sono entrambe pari a $e$. Per i moduli d'ordine successivi a questa riga, dovrai rispondere tenendo in considerazione anche questa nave.

Nella fase iniziale ci sono $0$ navi in servizio. Nell'input, le righe che rappresentano informazioni di servizio delle navi sono al massimo $1000$. Nota inoltre che tra due stesse isole possono operare più navi.

Output

Sia $m$ il numero di righe dell'input che rappresentano moduli d'ordine. L'output è composto da $m$ righe e, nella riga $i$ ($1 \le i \le m$), devi scrivere un intero che rappresenta la risposta all'$i$-esimo modulo d'ordine. Vale a dire, se è possibile viaggiare tra la partenza e la destinazione dell'$i$-esimo modulo d'ordine effettuando trasbordi tra più navi, scrivi il valore minimo della somma delle tariffe; se è impossibile viaggiare, scrivi $-1$.

Esempi di input e output

Esempio di input 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

Esempio di output 1

-1
15
12

Esempio di input 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

Esempio di output 2

5955
21431
9298
16392
24774
8840