Problème

Dans le pays de JOI, il y a $n$ îles, numérotées de $1$ à $n$. Actuellement, le développement d'un réseau de lignes maritimes reliant les îles entre elles est en cours dans le pays de JOI.

Vous travaillez dans une billetterie qui gère les billets de bateau. Dans le pays de JOI, de nombreuses personnes souhaitent voyager d'une île à l'autre en bateau au moindre coût possible ; elles inscrivent leur île de départ et leur île de destination sur un bon de commande et vous l'envoient.

Votre travail consiste, dès la réception d'un bon de commande d'un client, à calculer le tarif le moins cher parmi les itinéraires reliant le point de départ et la destination en prenant éventuellement plusieurs bateaux en correspondance, et à le communiquer au client. Toutefois, selon l'itinéraire, il est parfois impossible d'effectuer le voyage en bateau. Dans ce cas, vous devez informer le client qu'« il est impossible de voyager en bateau ». De plus, dans le pays de JOI, de nouveaux bateaux reliant les îles entrent régulièrement en service, et ces informations vous sont communiquées au fur et à mesure. Lorsque vous répondez aux clients, vous devez tenir compte des informations les plus récentes.

Étant donné en entrée les bons de commande des clients ainsi que les informations sur les nouveaux bateaux mis en service, écrivez un programme qui détermine les réponses à fournir aux clients.

Entrée

Sur la $1$-ère ligne de l'entrée sont écrits $2$ entiers $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Cela indique qu'il y a $n$ îles et que l'entrée comporte $k + 1$ lignes. Sur la $(i + 1)$-ème ligne ($1 \le i \le k$), $3$ ou $4$ entiers sont écrits, séparés par des espaces.

• Lorsque le premier nombre est $0$, cette ligne représente le bon de commande d'un client. Sur cette ligne sont écrits $3$ entiers $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) séparés par des espaces. Cela signifie qu'un client a envoyé un bon de commande ayant l'île $a$ comme point de départ et l'île $b$ comme destination.
• Lorsque le premier nombre est $1$, cette ligne représente les informations de mise en service d'un nouveau bateau. Sur cette ligne sont écrits $4$ entiers $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Cela signifie qu'un bateau effectuant l'aller-retour entre l'île $c$ et l'île $d$ vient d'entrer en service, et que le tarif de ce bateau de l'île $c$ vers l'île $d$ ainsi que de l'île $d$ vers l'île $c$ est égal à $e$. Pour les bons de commande situés après cette ligne, vous devez répondre en prenant également ce bateau en compte.

Au départ, $0$ bateau est en service. Dans l'entrée, le nombre de lignes représentant des informations de mise en service de bateaux est d'au plus $1000$. Notez également que plusieurs bateaux peuvent assurer la liaison entre deux mêmes îles.

Sortie

Soit $m$ le nombre de lignes représentant des bons de commande dans l'entrée. La sortie se compose de $m$ lignes et, sur la $i$-ème ligne ($1 \le i \le m$), vous devez écrire un entier représentant la réponse au $i$-ème bon de commande. Autrement dit, s'il est possible de voyager entre le point de départ et la destination du $i$-ème bon de commande en prenant un ou plusieurs bateaux, écrivez la somme minimale des tarifs ; s'il est impossible d'effectuer le voyage, écrivez $-1$.

Exemples d'entrée et de sortie

Exemple d'entrée 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

Exemple de sortie 1

-1
15
12

Exemple d'entrée 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

Exemple de sortie 2

5955
21431
9298
16392
24774
8840