Problem Background

In the northern Siberian tundra, there is a group of islands composed of \( N \) small islands, which we number sequentially from 1 to \( N \).

Problem Description

Initially, there are no air routes between the islands. As transportation develops, routes connecting two islands gradually emerge. For example, adding a route between island \( u \) and island \( v \) with a travel time of \( e \). Along this route, people from island \( u \) can travel to island \( v \) and vice versa, with a travel time of \( e \).

With the development of tourism, more and more people visit these islands. Consequently, the shortest path between two islands becomes a topic of great interest.

Input Format

The input consists of \( M+1 \) lines.

The first line contains two integers \( N \) and \( M \), representing the number of islands and the total number of operations, respectively.

The next \( M \) lines each describe an operation with the following formats:

• 0 s t: Queries the shortest travel time from island \( s \) to island \( t \) (\( 1 \le s \le n, 1 \le t \le n, s \neq t \)).
• 1 u v e: Adds a bidirectional route from island \( u \) to island \( v \) with a travel time of \( e \) (\( 1 \le u \le n, 1 \le v \le n, u \neq v, 1 \le e \le 10^6 \)).

Output Format

For each query, output a single line.

If there is no feasible route, output -1; otherwise, output the shortest travel time.

Sample Input and Output

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

Output Sample #1

-1
15
12

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

Output Sample #2

5955
21431
9298
16392
24774
8840

Notes

For 20% of the data, \( N \le 5 \) and \( M \le 30 \).

For 40% of the data, \( N \le 20 \) and \( M \le 200 \).

For 60% of the data, \( N \le 80 \) and \( M \le 500 \).

For 80% of the data, \( N \le 100 \) and \( M \le 2500 \).

For 100% of the data, \( N \le 100 \) and \( M \le 5000 \).

见题面 Input 部分

见题面 Output 部分