Aeolia Traffic Management: Shortest Path Queries

The kingdom of Aeolia has a complex network of city streets represented as an undirected graph with n intersections and m bidirectional roads. Due to heavy traffic, the government needs to impose restrictions on certain roads by changing their weights. Your task is to process a series of q queries. There are two types of queries:

• Type 1: Update the weight of the road between intersections u and v to w.
• Type 2: Compute the shortest path distance from intersection u to intersection v using the current road weights.

If there is no path between the specified intersections, output -1. Note that the distance from a node to itself is always \(0\).

The problem requires careful dynamic updating of the graph and using an efficient shortest path algorithm, such as Dijkstra's algorithm. For reference, the distance function can be formally defined as follows:

\[ \text{distance}(u,v)=\begin{cases} 0, & \text{if } u=v, \\ \min_{\text{paths } u \to v} \sum_{e \in \text{path}} w_e, & \text{otherwise} \end{cases} \]

Make sure your solution reads from standard input and writes to standard output.

inputFormat

The input is given from standard input and has the following format:

n m q
u1 v1 w1
u2 v2 w2
... (m lines for roads)
query1
query2
... (q queries)

Each road is specified by three integers u, v and w, indicating a bidirectional road between intersections u and v with weight w.

Each query is in one of the two following forms:

• 1 u v w: Update the weight of the road between u and v to w.
• 2 u v: Compute the shortest path distance from u to v.

outputFormat

For each query of type 2, print the shortest path distance on a separate line. If there is no obtainable path between the two intersections, output -1.

## sample

6 7 5
1 2 4
1 3 3
2 3 1
3 4 2
4 5 6
5 6 1
4 6 2
2 1 6
1 4 6 10
2 1 6
1 1 3 8
2 1 6

7
12
14

</p>