P2683 [AHOI2015 Middle School Division] Small Island

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

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.

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$).

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

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