Sea Journey

The country of JOI has $n$ islands, numbered from $1$ to $n$. A network of boat routes connecting the islands is being developed.

You work at a ticket office that handles boat tickets. Many people in JOI want to travel between islands as cheaply as possible by boat, and they send you order forms listing a departure island and a destination island.

Your job is: as soon as you receive an order form, compute the cheapest possible fare among all ways of traveling from the departure to the destination by transferring between boats, and report it to the customer.

Depending on the route, however, it may be impossible to travel by boat at all. In that case you must answer $-1$, meaning the trip is impossible. In addition, new boat routes between islands keep starting service in JOI, and you are told about them as they appear. Every answer you give must reflect the most up-to-date information.

Given the customers' order forms and the information about newly started boat routes as input, write a program that produces the answer for each order form.

The first line contains two integers $n$ and $k$ ($1 \le n \le 100$, $1 \le k \le 5000$): there are $n$ islands, followed by $k$ command lines.

Each of the next $k$ lines contains either $3$ or $4$ integers separated by spaces.

• If the first number is $0$, the line is a customer order form.
  • The line contains three integers $0$, $a$, $b$ ($1 \le a \le n$, $1 \le b \le n$, $a \ne b$).
  • It means a customer sent an order form with departure island $a$ and destination island $b$.
• If the first number is $1$, the line describes a boat route that has just started service.
  • The line contains four integers $1$, $c$, $d$, $e$ ($1 \le c \le n$, $1 \le d \le n$, $c \ne d$, $1 \le e \le 1000000$).
  • A boat running back and forth between islands $c$ and $d$ has started service; the fare from $c$ to $d$ and the fare from $d$ to $c$ are both $e$.
  • This boat must be taken into account for all order forms after this line.

Initially no boats are in service. At most $1000$ of the input lines describe boat routes. Note that several different boats may operate between the same pair of islands.

Let $m$ be the number of order-form lines in the input.

Print $m$ lines. Line $i$ ($1 \le i \le m$) contains an integer: the answer to the $i$-th order form.

That is, if it is possible to travel from the departure to the destination of the $i$-th order form by transferring between boats, print the minimum total fare; if it is impossible, print $-1$.

The figure below illustrates, for the first input, how the boat routes start service one by one and the answer given for each order form.