Taco

This problem involves processing multiple datasets that represent a dynamically constructed graph. In each dataset, you are given a number of intersections (nodes) and a series of operations. There are two types of operations:

• Update: Add an undirected road between two intersections with a specified length.
• Query: Calculate the shortest distance between two intersections using the current graph.

For each query operation, if a path exists, output the minimum distance; otherwise, output -1. The solution must use Dijkstra’s algorithm. Note that the time complexity for Dijkstra's algorithm is \(O(E \log V)\) where \(E\) is the number of edges and \(V\) is the number of vertices.

inputFormat

The input consists of multiple datasets. Each dataset begins with a line containing two integers (m) and (q), where (m) is the number of intersections and (q) is the number of operations. This is followed by (q) lines, each representing an operation. An operation is given in one of the following formats:

1. "1 a b l" means adding an undirected road between intersections (a) and (b) with length (l).
2. "0 x y" means a query for the shortest path from intersection (x) to intersection (y).

The end of the input is denoted by a line with "0 0".

outputFormat

For each query in the order they appear, output a single line containing the shortest distance between the specified intersections. If no path exists, output -1. There should be no extra output.## sample

4 5
1 1 2 10
1 2 3 20
0 1 3
1 3 4 25
0 1 4
3 3
0 1 2
1 1 2 15
0 1 3
0 0

30
55
-1
-1