A11141 | Diverging Directions

You are given a directed weighted graph with $n$ nodes and $2n-2$ edges. The nodes are labeled from $1$ to $n$ , while the edges are labeled from $1$ to $2n-2$ . The graph's edges can be split into two parts.

- The first $n-1$ edges will form a rooted spanning tree, with node $1$ as the root. All these edges will point away from the root.
- The last $n-1$ edges will be from node $i$ to node $1$ , for all $2<=i<=n$ .

You are given $q$ queries. There are two types of queries

- $1\ i\ w$ : Change the weight of the $i$ -th edge to $w$
- $2\ u\ v$ : Print the length of the shortest path between nodes $u$ to $v$

Given these queries, print the shortest path lengths.

The first line of input will contain two integers $n,q$ ( $2<=n,q<=200000$ ), the number of nodes, and the number of queries, respectively.

The next $2n-2$ integers will contain 3 integers $a_{i},b_{i},c_{i}$ , denoting a directed edge from node $a_{i}$ to node $b_{i}$ with weight $c_{i}$ .

The first $n-1$ of these lines will describe a rooted spanning tree pointing away from node $1$ , while the last $n-1$ of these lines will have $b_{i}=1$ .

More specifically,

- The edges $(a_{1},b_{1}),(a_{2},b_{2}),...\ (a_{n-1},b_{n-1})$ will describe a rooted spanning tree pointing away from node $1$ .
- $b_{j}=1$ for $n<=j<=2n-2$ .
- $a_{n},a_{n+1},...,a_{2n-2}$ will be distinct and between $2$ and $n$ .

The next $q$ lines will contain 3 integers, describing a query in the format described in the statement.

All edge weights will be between $1$ and $10^{6}$ .

For each type 2 query, print the length of the shortest path in its own line.