P4949 Shortest Distance.

You are given an undirected connected graph with $n$ vertices and $n$ edges. You need to support two types of operations: 1. Modify the length of the $x$-th edge to $y$. 2. Query the shortest distance from vertex $x$ to vertex $y$. There are $m$ operations in total.

The input has a total of $n+m+1$ lines: Line $1$ contains two positive integers $n,m$, representing the number of vertices (which is also the number of edges) and the number of operations. Lines $2$ to $n+1$ each contain three positive integers $x,y,z$, indicating that there is an edge of length $z$ between $x$ and $y$. Lines $n+2$ to $n+m+1$ each contain three positive integers $opt,x,y$, representing the type of operation and its parameters (see the meaning in the “Description”).

For each operation of type $2$, output the query result.

 For $100\%$ of the testdata, it is guaranteed that $z\in [0,5000]$. Translated by ChatGPT 5