Умова задачі

У країні JOI є $n$ островів, пронумерованих від $1$ до $n$. Наразі в країні JOI триває розбудова мережі морських маршрутів, що з'єднують острови між собою.

Ви працюєте в квитковому центрі, який займається продажем квитків на судна. У країні JOI є багато людей, які хочуть подорожувати між островами на суднах якомога дешевше; вони вписують пункт відправлення та пункт призначення у бланк замовлення і надсилають його вам.

Ваша робота полягає в тому, щоб одразу після отримання бланка замовлення від клієнта обчислити найдешевшу вартість проїзду серед маршрутів, які з'єднують пункт відправлення і пункт призначення з можливими пересадками між кількома суднами, і повідомити її клієнту. Проте залежно від маршруту може статися, що подорожувати суднами неможливо. У такому разі потрібно повідомити клієнту, що «подорожувати суднами неможливо». Крім того, у країні JOI одне за одним починають курсувати нові судна, які з'єднують острови, і ця інформація своєчасно надходить до вас. Відповідаючи клієнтам, ви повинні враховувати найновішу інформацію.

Напишіть програму, яка за заданими бланками замовлень клієнтів та інформацією про початок курсування нових суден визначає відповіді клієнтам.

Вхідні дані

У $1$-му рядку вхідних даних записано $2$ цілі числа $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Це означає, що кількість островів дорівнює $n$, а вхідні дані складаються з $k + 1$ рядків. У $(i + 1)$-му рядку ($1 \le i \le k$) через пробіл записано $3$ або $4$ цілі числа.

• Коли перше число дорівнює $0$, цей рядок позначає бланк замовлення клієнта. У цьому рядку через пробіл записано $3$ цілі числа $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$). Це означає, що клієнт надіслав бланк замовлення з островом $a$ як пунктом відправлення та островом $b$ як пунктом призначення.
• Коли перше число дорівнює $1$, цей рядок позначає інформацію про нове судно, що почало курсувати. У цьому рядку записано $4$ цілі числа $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Це означає, що почало курсувати нове судно, яке здійснює рейси туди й назад між островом $c$ та островом $d$, причому вартість проїзду цим судном як від острова $c$ до острова $d$, так і від острова $d$ до острова $c$ дорівнює $e$. Для бланків замовлень після цього рядка потрібно давати відповідь, враховуючи також і це судно.

На початковому етапі курсує $0$ суден. У вхідних даних кількість рядків, що містять інформацію про курсування суден, не перевищує $1000$. Також зверніть увагу, що між двома островами може курсувати кілька суден.

Вихідні дані

Нехай кількість рядків, які позначають бланки замовлень у вхідних даних, дорівнює $m$. Вихідні дані складаються з $m$ рядків; в $i$-му рядку ($1 \le i \le m$) запишіть ціле число, яке становить відповідь на $i$-й бланк замовлення. Тобто, якщо між пунктом відправлення і пунктом призначення $i$-го замовлення можна подорожувати, пересідаючи між кількома суднами, запишіть мінімальну сумарну вартість проїзду. Якщо подорожувати неможливо, запишіть $-1$.

Приклади вхідних і вихідних даних

Приклад вхідних даних 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

Приклад вихідних даних 1

-1
15
12

Приклад вхідних даних 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

Приклад вихідних даних 2

5955
21431
9298
16392
24774
8840