Illya likes graphs a lot. His favourite type of graph is tree. Illya invented many problems with it, but he can't solve them. He asked you to solve one of them.

You are given a weighted tree T with n nodes. The tree is rooted at node 1. You are also given q queries to it. Queries can be one of two types:

1 i z - change the weight of i-th edge to z.

2 v - find the maximum distance between two distinct nodes in the subtree of node v.

Input:

The first line of input contains two integers n and q. The next n-1 lines contain three integers x, y, z, denoting an undirected edge from x to y with weight z. Next q lines contains queries as described above.

Output:

For each query of 2nd type output answer for it in a single line.

Constraints:

1 ≤ n, q ≤ 10⁵

1 ≤ x, y, v ≤ n

1 ≤ i ≤ n-1

1 ≤ z ≤ 10⁹