Tree and Easy Queries

Bru was shocked by how hard the other problems were, so he decided to write a problem that participants with low skill, like himself, could enjoy.

A tree is given. Process the following two kinds of queries.

• 1 k x: Change the length of edge $k$ to $x$.
• 2 p: Print the length of the longest simple path that passes through vertex $p$.

A simple path is a path that does not pass through any vertex more than once.

Vertices are numbered starting from 1.

The first line contains the number of vertices $N$ and the number of queries $Q$. ($2 \le N, Q \le 150{,}000$)

From the second line through line $N$, the next $N-1$ lines give the edges from edge 1 to edge $N-1$, in order. For each edge, the two vertices it connects, $u_i$ and $v_i$, and the edge length $d_i$ are given in that order. ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le d_i \le 10^9$)

From line $N+1$ through line $N+Q$, the queries are given. Each query is one of the two kinds described above. ($1 \le k < N$, $1 \le x \le 10^9$, $1 \le p \le N$)

The given tree is guaranteed to be a valid tree. Also, at least one query of type 2 is guaranteed.

For each query of type 2, print the answer on its own line.