Problem Description

JOI Kingdom has $ n $ islands, each labeled with numbers from $ 1 $ to $ n $. Currently, the development of shipping routes connecting these islands is underway.

You work at a ticket center that handles boat tickets. Many people in JOI Kingdom want to travel between islands as cheaply as possible using boats. They fill out order forms with their departure and destination islands and send them to you.

Your job is to immediately calculate the cheapest fare for the route connecting the departure and destination islands, considering multiple boat transfers, and inform the customers.

However, depending on the itinerary, it might not be possible to travel using boats. In such cases, you need to inform the customers that traveling by boat is not possible. Also, new boats keep starting their operations between islands, and you receive this information periodically. You must ensure that your responses to customers are based on the latest information.

Create a program that, given customer order forms and new boat operation information, provides the appropriate response to the customers.

Note that an illustration of the execution scenario for Input Example 1 and Output Example 1 is provided as Figure 1.

Input Format

The first line of input contains two integers $n,\ k$ ($1 \leq n \leq 100$, $1 \leq k \leq 5,000$), indicating that there are $ n $ islands and the input consists of $ k + 1 $ lines.

The $ i + 1 $ line ($1 \leq i \leq k$) contains three or four integers separated by spaces.

• If the first number is $ 0 $, this line represents a customer's order form.
  This line contains three integers $0,\ a,\ b$ ($1 \leq a \leq n$, $1 \leq b \leq n$, $a \neq b$).
  This indicates that the customer has sent an order form with island $ a $ as the departure and island $ b $ as the destination.
• If the first number is $ 1 $, this line represents new boat operation information.
  This line contains four integers $1,\ c,\ d,\ e$ ($1 \leq c \leq n$, $1 \leq d \leq n$, $c \neq d$, $1 \leq e \leq 1,000,000$).
  This indicates that a new boat has started operating between islands $ c $ and $ d $, with both fares from island $ c $ to $ d $ and from island $ d $ to $ c $ being $ e $.
  For order forms received after this line, this boat must be considered in the responses.

Initially, no boats are operating. Note that there are at most $ 1,000 $ lines representing boat operation information in the input. Also, be aware that there can be multiple boats operating between the same pair of islands.

Output Format

Let $ m $ be the number of lines in the input representing order forms.
The output consists of $ m $ lines, where the $ i $ line ($1 \leq i \leq m$) contains an integer representing the response to the $ i $ order form.
That is, if it is possible to travel between the departure and destination islands using multiple boats, write the minimum total fare. If it is not possible 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

Notes/Hints

Sample Explanation 1

An illustration of the progression of new boat operations and responses to customer order forms for Input Example 1 and Output Example 1 is provided as Figure 1.

见题面 Input 部分

见题面 Output 部分