Zadanie

W kraju JOI znajduje się $n$ wysp ponumerowanych od $1$ do $n$. Obecnie w kraju JOI trwa rozbudowa sieci połączeń żeglugowych łączących poszczególne wyspy.

Pracujesz w centrum biletowym zajmującym się sprzedażą biletów na statki. W kraju JOI jest wielu ludzi, którzy chcą podróżować statkami między wyspami jak najtaniej; wpisują oni miejsce wypłynięcia oraz cel podróży na formularzu zamówienia i przesyłają go do Ciebie.

Twoim zadaniem jest, natychmiast po otrzymaniu formularza zamówienia od klienta, obliczenie najniższej opłaty spośród tras łączących miejsce wypłynięcia z celem podróży z ewentualnymi przesiadkami między kilkoma statkami i przekazanie tej informacji klientowi. W zależności od trasy może się jednak zdarzyć, że podróż statkiem nie jest możliwa. Wówczas należy poinformować klienta, że „podróż statkiem jest niemożliwa”. Ponadto w kraju JOI kolejne nowe statki łączące wyspy rozpoczynają kursowanie, a informacje o tym są Ci na bieżąco przekazywane. Odpowiadając klientom, musisz uwzględniać najbardziej aktualne informacje.

Napisz program, który na podstawie podanych na wejściu formularzy zamówień klientów oraz informacji o nowo uruchomionych połączeniach statków wyznaczy odpowiedzi dla klientów.

Wejście

W $1$. wierszu wejścia zapisane są $2$ liczby całkowite $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Oznaczają one, że liczba wysp wynosi $n$, a wejście składa się z $k + 1$ wierszy. W $(i + 1)$-szym wierszu ($1 \le i \le k$) zapisane są $3$ lub $4$ liczby całkowite oddzielone spacjami.

• Gdy pierwszą liczbą jest $0$, wiersz ten oznacza formularz zamówienia klienta. W wierszu tym zapisane są $3$ liczby całkowite $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) oddzielone spacjami. Oznacza to, że klient przysłał formularz zamówienia z wyspą $a$ jako miejscem wypłynięcia i wyspą $b$ jako celem podróży.
• Gdy pierwszą liczbą jest $1$, wiersz ten oznacza informację o nowym statku rozpoczynającym kursowanie. W wierszu tym zapisane są $4$ liczby całkowite $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Oznacza to, że statek kursujący w obie strony między wyspą $c$ a wyspą $d$ właśnie rozpoczął kursowanie, a opłata za przejazd tym statkiem z wyspy $c$ na wyspę $d$ oraz z wyspy $d$ na wyspę $c$ wynosi $e$. Dla formularzy zamówień występujących po tym wierszu należy udzielać odpowiedzi z uwzględnieniem również tego statku.

W fazie początkowej kursuje $0$ statków. Wśród wierszy wejścia liczba wierszy opisujących informacje o kursowaniu statków wynosi co najwyżej $1000$. Zwróć też uwagę, że między tą samą parą wysp może kursować wiele statków.

Wyjście

Niech $m$ oznacza liczbę wierszy opisujących formularze zamówień na wejściu. Wyjście składa się z $m$ wierszy, a w $i$-tym wierszu ($1 \le i \le m$) należy zapisać liczbę całkowitą oznaczającą odpowiedź na $i$-ty formularz zamówienia. To znaczy, jeśli podróż między miejscem wypłynięcia a celem podróży z $i$-tego formularza zamówienia z przesiadkami między statkami jest możliwa, należy wypisać minimalną sumę opłat; jeśli podróż jest niemożliwa, należy wypisać $-1$.

Przykłady wejścia i wyjścia

Przykład wejścia 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

Przykład wyjścia 1

-1
15
12

Przykład wejścia 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

Przykład wyjścia 2

5955
21431
9298
16392
24774
8840