Task
JOI country consists of n islands which are numbered from 1 to n. The country is now developping the
ship network between these islands.
You are working at a ticket center of these ships. Many people thinks of making a trip to another
island as cheep as possible. They write the islands of departure and destinations of their trip in the
order forms and send them to you.
Your task is answering to the query from the clients, by calculating the lowest possible cost to reach
their destination from their departure island by using the ships. In some case that the trip by the ships is
impossible, you must tell it to your client. Moreover, in this country, many ship lines are beginning one
after another, and you are passed on the information about new ships at any time. So you must check
the latest information carefully to answer to your clients.
You are given a list of the order forms from clients and information of new ships, sorted by time.
Write a program that calculates the answer to your clients.

Input

The format of each input file is as follows.
Line 1 consists of 2 space-separated integers: the number n (1
n
100) of islands, and the
number k (1 k 5000) of following lines in the input (input consists of k + 1 lines).
Line i + 1 (1 i k) consists of 3 or 4 space-separated integers:
• If the first number is 0, the line represents a order form. The line consists of 3 integers 0, a, b
(1 a n, 1 b n, a b). This means that a client has sent the order form of a trip from
island a to island b.
• If the first number is 1, the line represents a new ship. The line consists of 4 integers 1, c, d, e
(1 c n, 1 d n, c d, 1 e 1000000). This means that a new ship line connecting
island c and d has begun, and the fare of c to d and d to c are both e. For the queries in the rest
of the input, this ship also must be taken in consideration.
In the beginning, no ship is running. In the input, the number of lines representing information
of new ship is not more than 1000. There may be two or more ships between the same pair of
islands.

Output

The format of each output file to submit is as follows. The file consists of m lines. Line i (1 i m)
should contain one integer representing the answer to i-th order form. This means, if the trip in i-th
order form is possible by some ships, write the minimum possible value of total fare, and other wise,
write -1.

Example

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

Output:
5955 
21431 
9298 
16392 
24774 
8840