{"raw_statement":[{"iden":"problem statement","content":"You are given a tree $T$ with $N$ vertices. Edge $i$ $(1\\leq i\\leq N-1)$ connects vertices $u _ i$ and $v _ i$, and has a weight of $w _ i$.\nProcess $Q$ queries in order. There are two kinds of queries as follows.\n\n*   `1 i w` : Change the weight of edge $i$ to $w$.\n*   `2 u v`：Print the distance between vertex $u$ and vertex $v$.\n\nHere, the distance between two vertices $u$ and $v$ of a tree is the smallest total weight of edges in a path whose endpoints are $u$ and $v$."},{"iden":"constraints","content":"*   $1\\leq N\\leq 2\\times10^5$\n*   $1\\leq u _ i,v _ i\\leq N\\ (1\\leq i\\leq N-1)$\n*   $1\\leq w _ i\\leq 10^9\\ (1\\leq i\\leq N-1)$\n*   The given graph is a tree.\n*   $1\\leq Q\\leq 2\\times10^5$\n*   For each query of the first kind,\n    *   $1\\leq i\\leq N-1$, and\n    *   $1\\leq w\\leq 10^9$.\n*   For each query of the second kind,\n    *   $1\\leq u,v\\leq N$.\n*   There is at least one query of the second kind.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$u _ 1$ $v _ 1$ $w _ 1$\n$u _ 2$ $v _ 2$ $w _ 2$\n$\\vdots$\n$u _ {N-1}$ $v _ {N-1}$ $w _ {N-1}$\n$Q$\n$\\operatorname{query} _ 1$\n$\\operatorname{query} _ 2$\n$\\vdots$\n$\\operatorname{query} _ Q$\n\nHere, $\\operatorname{query} _ i$ denotes the $i$\\-th query and is in one of the following format:\n\n$1$ $i$ $w$\n\n$2$ $u$ $v$"},{"iden":"sample input 1","content":"5\n1 2 3\n1 3 6\n1 4 9\n4 5 10\n4\n2 2 3\n2 1 5\n1 3 1\n2 1 5"},{"iden":"sample output 1","content":"9\n19\n11\n\nThe initial tree is shown in the figure below.\n![image](https://img.atcoder.jp/abc294/b11e5bebc4d34f82fc3cd43899df453b.png)\nEach query should be processed as follows.\n\n*   The first query asks you to print the distance between vertex $2$ and vertex $3$. Edge $1$ and edge $2$, in this order, form a path between them with a total weight of $9$, which is the minimum, so you should print $9$.\n*   The second query asks you to print the distance between vertex $1$ and vertex $5$. Edge $3$ and edge $4$, in this order, form a path between them with a total weight of $19$, which is the minimum, so you should print $19$.\n*   The third query changes the weight of edge $3$ to $1$.\n*   The fourth query asks you to print the distance between vertex $1$ and vertex $5$. Edge $3$ and edge $4$, in this order, form a path between them with a total weight of $11$, which is the minimum, so you should print $11$."},{"iden":"sample input 2","content":"7\n1 2 1000000000\n2 3 1000000000\n3 4 1000000000\n4 5 1000000000\n5 6 1000000000\n6 7 1000000000\n3\n2 1 6\n1 1 294967296\n2 1 6"},{"iden":"sample output 2","content":"5000000000\n4294967296\n\nNote that the answers may not fit into $32$\\-bit integers."},{"iden":"sample input 3","content":"1\n1\n2 1 1"},{"iden":"sample output 3","content":"0"},{"iden":"sample input 4","content":"8\n1 2 105\n1 3 103\n2 4 105\n2 5 100\n5 6 101\n3 7 106\n3 8 100\n18\n2 2 8\n2 3 6\n1 4 108\n2 3 4\n2 3 5\n2 5 5\n2 3 1\n2 4 3\n1 1 107\n2 3 1\n2 7 6\n2 3 8\n2 1 5\n2 7 6\n2 4 7\n2 1 7\n2 5 3\n2 8 6"},{"iden":"sample output 4","content":"308\n409\n313\n316\n0\n103\n313\n103\n525\n100\n215\n525\n421\n209\n318\n519"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}