Background

In the frigid lands of northern Siberia lies an archipelago consisting of $N$ small islands, which we number from $1$ to $N$ in order.

Problem Description

At first, there are no routes between the islands. Later, as transportation develops, routes connecting pairs of islands gradually appear. For example, when a route between island $u$ and island $v$ is added with travel time $e$, people on island $u$ can travel to island $v$, and people on island $v$ can also travel to island $u$, with time $e$ along this route.

Meanwhile, with the growth of tourism, more and more people come to visit. The shortest path between two islands has therefore become a topic of great interest.

Input Format

The input has $M+1$ lines.

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

Each of the next $M$ lines describes one operation, in one of the following formats:

0 s t: Query the shortest travel time from island $s$ to island $t$ ($1 \le s \le N$, $1 \le t \le N$, $s \ne t$).

1 u v e: Add a new bidirectional route between island $u$ and island $v$ with travel time $e$ ($1 \le u \le N$, $1 \le v \le N$, $u \ne v$, $1 \le e \le 10^6$).

Output Format

For each query, output one line.

For each query, if no feasible path exists, output -1; otherwise, output the shortest travel time.

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

-1
15
12

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

5955
21431
9298
16392
24774
8840

Hint

For $20\%$ of the testdata, $N \le 5$ and $M \le 30$.

For $40\%$ of the testdata, $N \le 20$ and $M \le 200$.

For $60\%$ of the testdata, $N \le 80$ and $M \le 500$.

For $80\%$ of the testdata, $N \le 100$ and $M \le 2500$.

For $100\%$ of the testdata, $N \le 100$ and $M \le 5000$.

Translated by ChatGPT 5