Problema

En el país de JOI hay $n$ islas, y cada isla está numerada del $1$ al $n$. Actualmente, en el país de JOI se está desarrollando una red de rutas marítimas que conecta las islas entre sí.

Trabajas en un centro de boletos que gestiona pasajes de barco. En el país de JOI hay muchas personas que desean viajar entre islas en barco de la forma más económica posible; ellas anotan el lugar de partida y el destino en un formulario de pedido y te lo envían.

Tu trabajo consiste en que, tan pronto como recibas un formulario de pedido de un cliente, calcules la tarifa más barata entre las rutas que conectan el punto de partida y el destino haciendo transbordo entre varios barcos, y se la comuniques al cliente. Sin embargo, según el itinerario, puede haber casos en los que no sea posible viajar en barco. En ese caso, es necesario informar al cliente que «no es posible viajar en barco». Además, en el país de JOI entran en funcionamiento continuamente nuevos barcos que conectan islas entre sí, y esa información se te comunica en cada momento. Al responder a los clientes, debes tener en cuenta la información más reciente.

Dados como entrada los formularios de pedido de los clientes y la información de operación de los barcos que entran en funcionamiento, escribe un programa que determine las respuestas para los clientes.

Entrada

En la línea $1$ de la entrada están escritos $2$ enteros $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Esto indica que el número de islas es $n$ y que la entrada consta de $k + 1$ líneas. En la línea $(i + 1)$ ($1 \le i \le k$) están escritos $3$ o $4$ enteros separados por espacios.

• Cuando el primer número es $0$, esta línea representa el formulario de pedido de un cliente. En esta línea están escritos $3$ enteros $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) separados por espacios. Esto indica que un cliente ha enviado un formulario de pedido con la isla $a$ como punto de partida y la isla $b$ como destino.
• Cuando el primer número es $1$, esta línea representa la información de un barco que acaba de iniciar su operación. En esta línea están escritos $4$ enteros $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Esto indica que un barco que realiza viajes de ida y vuelta entre la isla $c$ y la isla $d$ ha comenzado a operar, y que tanto la tarifa de la isla $c$ a la isla $d$ como la tarifa de la isla $d$ a la isla $c$ en este barco son iguales a $e$. Para los formularios de pedido posteriores a esta línea, debes responder teniendo también en cuenta este barco.

En la etapa inicial, hay $0$ barcos operando. En la entrada, el número de líneas que representan información de operación de barcos es a lo sumo $1000$. Asimismo, ten en cuenta que pueden operar varios barcos entre un mismo par de islas.

Salida

Sea $m$ el número de líneas que representan formularios de pedido en la entrada. La salida consta de $m$ líneas, y en la línea $i$ ($1 \le i \le m$) debes escribir un entero que represente la respuesta al $i$-ésimo formulario de pedido. Es decir, si es posible viajar entre el punto de partida y el destino del $i$-ésimo formulario de pedido haciendo transbordo entre varios barcos, escribe el valor mínimo de la suma de sus tarifas; si es imposible viajar, escribe $-1$.

Ejemplos de entrada y salida

Ejemplo de entrada 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

Ejemplo de salida 1

-1
15
12

Ejemplo de entrada 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

Ejemplo de salida 2

5955
21431
9298
16392
24774
8840