L. Hosen and The Magical Tree!
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the famous $$$\textit{Uncling}$$$ city, there is a small school called the $$$\textit{Uncling}$$$ school. Hosen is a student in that school and he loves all the subjects except one and only subject... Yes, its Trees.

Eyad and Jaber are such bad bullies; they keep bullying Hosen and give him hard tree problems. $$$\textit{Stop it! I hate trees!}$$$ Hosen said. Hosen wants to take revenge on them and show them how good he can become at Trees! He decided to take the risk and... No, he won't study Trees. He will go to the magical forest to get the power of Trees from the magical grand tree.

After climbing so many trees, he finally reached the magical tree. Unfortunately, the magical grand tree will not give him the power so easily. In order to get the power of Trees, you must solve this problem! the magical grand tree said. As expected, its a tree problem :( Hosen needs help solving the problem; please help him!!

The magical grand tree will give Hosen $$$Q$$$ queries and a tree consisting of $$$N$$$ vertices and weighted edges. The distance between two vertices $$$u$$$ and $$$v$$$ in the given tree is the sum of weights of edges on the simple path between $$$u$$$ and $$$v$$$. Hosen should respond to the queries and maintain the given tree. The queries are of two types as described in the following:

  • $$$1$$$ $$$i$$$ $$$x$$$ : change the weight of the $$$i$$$-th edge to $$$x$$$.
  • $$$2$$$ $$$u$$$ $$$v$$$ : print the following sum: $$$$$$\sum_{x = 1}^N dist_x(u, v)$$$$$$
Where $$$dist_x(u, v)$$$ is the distance from vertex $$$x$$$ to the closest vertex $$$c$$$ to it, where $$$c$$$ belongs to the simple path between vertices $$$u$$$ and $$$v$$$.
Input

The first line contains two positive integers $$$N$$$, $$$Q$$$, ($$$1 \le N, Q \le 10^5$$$), the number of vertices of the given tree, and the number of queries.

The following $$$N - 1$$$ lines contain three positive integers: $$$u$$$, $$$v$$$, $$$w$$$, ($$$1 \le u, v \le N$$$), ($$$1 \le w \le 10^8$$$), describing an edge between $$$u$$$ and $$$v$$$ having weight $$$w$$$.

The following $$$Q$$$ lines describe the queries in the form mentioned above, ($$$1 \le i \le N - 1$$$), ($$$1 \le u, v \le N$$$), ($$$1 \le x \le 10^8$$$).

Output

For each query of the second type, print the answer to that query on a separate line.

Examples
Input
3 3
1 2 5
2 3 5
1 1 10
2 1 2
2 1 3
Output
5
0
Input
7 5
1 2 1
1 3 2
2 4 1
2 5 3
3 6 2
1 7 3
2 1 7
2 1 6
1 2 1
2 1 7
2 1 6
Output
13
10
11
10