Diverging Directions

- 给出一个 $n$ 个点，$2n-2$ 条边的带权有向图。边分为两类： 1. 前 $n-1$ 条边构成一棵生成树，$1$ 为其根结点，每条边从父亲连向儿子。 2. 后 $n-1$ 条边从 $i$ 号结点连向 $1$ 号结点，$2\le i\le n$。 - 有 $m$ 次操作，每次操作为将第 $i$ 条边的边权改为 $w$ 或查询 $u$ 到 $v$ 的最短路。 - $1\le n,m\le 2\times 10^5$，任意时刻边权 $\le 10^6$。

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.

5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4

0
1
4
8
100
132
10