Aufgabe

Im Land JOI gibt es $n$ Inseln, die von $1$ bis $n$ nummeriert sind. Derzeit wird im Land JOI das Liniennetz für Schiffe zwischen den einzelnen Inseln ausgebaut.

Sie arbeiten in einem Ticketcenter, das Schiffsfahrkarten verkauft. Im Land JOI gibt es viele Menschen, die so kostengünstig wie möglich mit dem Schiff von Insel zu Insel reisen möchten; sie tragen ihren Startort und ihren Zielort in ein Bestellformular ein und senden es Ihnen zu.

Ihre Aufgabe ist es, sofort nach Erhalt eines Bestellformulars von einem Kunden unter allen Verbindungen, die Startort und Zielort durch Umsteigen zwischen mehreren Schiffen verbinden, den günstigsten Fahrpreis zu berechnen und dem Kunden mitzuteilen. Je nach Reiseroute kann es jedoch vorkommen, dass eine Reise mit dem Schiff nicht möglich ist. In diesem Fall müssen Sie dem Kunden mitteilen, dass „eine Reise mit dem Schiff nicht möglich ist“. Außerdem nehmen im Land JOI nach und nach neue Schiffe den Betrieb zwischen den Inseln auf, worüber Sie laufend informiert werden. Wenn Sie den Kunden antworten, müssen Sie stets die neuesten Informationen berücksichtigen.

Schreiben Sie ein Programm, das bei Eingabe der Bestellformulare der Kunden sowie der Betriebsinformationen neu eingesetzter Schiffe die Antworten an die Kunden berechnet.

Eingabe

In der $1$. Zeile der Eingabe stehen $2$ ganze Zahlen $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Dies bedeutet, dass es $n$ Inseln gibt und die Eingabe aus $k + 1$ Zeilen besteht. In der $(i + 1)$. Zeile ($1 \le i \le k$) stehen durch Leerzeichen getrennt $3$ oder $4$ ganze Zahlen.

• Wenn die erste Zahl $0$ ist, stellt diese Zeile das Bestellformular eines Kunden dar. In dieser Zeile stehen durch Leerzeichen getrennt $3$ ganze Zahlen $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$). Dies bedeutet, dass ein Kunde ein Bestellformular mit Insel $a$ als Startort und Insel $b$ als Zielort geschickt hat.
• Wenn die erste Zahl $1$ ist, stellt diese Zeile die Betriebsinformation eines neu in Betrieb genommenen Schiffes dar. In dieser Zeile stehen $4$ ganze Zahlen $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Dies bedeutet, dass ein Schiff, das zwischen Insel $c$ und Insel $d$ pendelt, neu den Betrieb aufgenommen hat und der Fahrpreis dieses Schiffes sowohl von Insel $c$ nach Insel $d$ als auch von Insel $d$ nach Insel $c$ jeweils $e$ beträgt. Für alle nachfolgenden Bestellformulare muss dieses Schiff bei der Antwort mitberücksichtigt werden.

Zu Beginn sind $0$ Schiffe in Betrieb. Unter den Eingabezeilen gibt es höchstens $1000$ Zeilen, die Betriebsinformationen von Schiffen darstellen. Beachten Sie außerdem, dass zwischen zwei Inseln auch mehrere Schiffe verkehren können.

Ausgabe

Sei $m$ die Anzahl der Zeilen in der Eingabe, die Bestellformulare darstellen. Die Ausgabe besteht aus $m$ Zeilen; schreiben Sie in die $i$. Zeile ($1 \le i \le m$) eine ganze Zahl, die die Antwort auf das $i$. Bestellformular darstellt. Das heißt: Wenn es möglich ist, zwischen Startort und Zielort des $i$. Bestellformulars durch Umsteigen zwischen mehreren Schiffen zu reisen, geben Sie die minimale Summe der Fahrpreise aus. Wenn eine Reise unmöglich ist, geben Sie $-1$ aus.

Ein- und Ausgabebeispiele

Eingabebeispiel 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

Ausgabebeispiel 1

-1
15
12

Eingabebeispiel 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

Ausgabebeispiel 2

5955
21431
9298
16392
24774
8840