Problem Description

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.

Input Format

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

Output Format

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

4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

13
12
26
16

Hint

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

Translated by ChatGPT 5