Условие задачи

В стране 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