Graph Operations

Given an undirected connected graph with \(n\) nodes 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 node \(x\) to node \(y\).

There are \(m\) operations in total.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of nodes (and edges) and the number of operations, respectively.

Then \(n\) lines follow, each containing three integers \(u\), \(v\), \(w\), which denote an edge between nodes \(u\) and \(v\) with length \(w\).

After that, \(m\) lines follow, each corresponding to an operation in one of the two formats below:

• 1 x y: Update the length of the \(x\)-th edge to \(y\).
• 2 x y: Query the shortest distance from node \(x\) to node \(y\).

outputFormat

For every query operation (i.e. when the operation type is 2), output a single line containing the shortest distance between the specified nodes.

sample

3 5
1 2 3
2 3 4
3 1 5
2 1 2
1 2 1
2 1 3
1 3 2
2 2 3

3
4
1