Problem

In the country of JOI, there are $n$ islands, and each island is numbered from $1$ to $n$. Currently, in the country of JOI, the development of a route network connecting the islands is underway.

You work at a ticket center that handles boat tickets. In the country of JOI, there are many people who wish to travel between islands by boat as cheaply as possible; they fill in their departure island and destination island on an order form and send it to you.

Your job is, immediately upon receiving an order form from a customer, to calculate the cheapest fare among the routes connecting the departure island and the destination island by transferring between several boats, and inform the customer. However, depending on the itinerary, it may be impossible to travel by boat. In that case, it is necessary to inform the customer that "it is impossible to travel by boat". Furthermore, in the country of JOI, new boats connecting islands are starting operation one after another, and you are informed of this information from time to time. When replying to customers, you must keep the latest information in mind.

Given customers' order forms and operation information on newly operating boats as input, write a program that finds the replies to the customers.

Input

On the $1$-st line of the input, $2$ integers $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$) are written. This indicates that the number of islands is $n$ and the input consists of $k + 1$ lines. On the $(i + 1)$-th line ($1 \le i \le k$), $3$ or $4$ integers are written separated by spaces.

• When the first number is $0$, this line represents a customer's order form. On this line, $3$ integers $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) are written separated by spaces. This means that a customer has sent an order form with island $a$ as the departure point and island $b$ as the destination.
• When the first number is $1$, this line represents operation information on a newly operating boat. On this line, $4$ integers $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$) are written. This means that a boat making round trips between island $c$ and island $d$ has newly started operation, and the fare of this boat from island $c$ to island $d$ and the fare from island $d$ to island $c$ are both $e$. For order forms from this line onward, you must reply while also taking this boat into consideration.

At the initial stage, $0$ boats are operating. Among the input lines, the number of lines representing boat operation information is at most $1000$. Also, note that multiple boats may operate between the same pair of islands.

Output

Let $m$ be the number of lines representing order forms in the input. The output consists of $m$ lines, and on the $i$-th line ($1 \le i \le m$), write an integer representing the reply to the $i$-th order form. That is, if it is possible to travel between the departure point and destination of the $i$-th order form by transferring between several boats, write the minimum total fare. If it is impossible to travel, write $-1$.

Sample Input and Output

Sample Input 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

Sample Output 1

-1
15
12

Sample Input 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

Sample Output 2

5955
21431
9298
16392
24774
8840