You are given an undirected tree consisting of n nodes with weights assigned to edges. You need to perform queries of two types:

1. Add a given value ai to all edges on the path from node vi to node ui. There will be no more than 500 queries of this type in the input.
2. Compute the sum of weights of all edges for which both endpoints are at distance no more than ki from node vi. The distance between two nodes is the number of edges on the path between them.

You should perform these queries in the given order and for each query of second type, print the computed value.

Input

The first line contains two integers n and q (1 ≤ n ≤ 1000, 0 ≤ q ≤ 500000) which are the number of nodes in the tree and the number of queries, respectively. The next n - 1 lines contain the description of the tree: i-thof these lines contains three integers vi, ui and wi (1 ≤ vi, ui ≤ n, 1 ≤ wi ≤ 100000) which are the number of nodes this edge connects and its weight, respectively. It is guaranteed that the given graph is a tree.

The following q lines contain the description of queries. On each of these lines, the first integer ti is the type of the query (1 ≤ ti ≤ 2). If ti = 1, it is followed by three integers vi, ui and ai (1 ≤ vi, ui ≤ n, 1 ≤ ai ≤ 100000) and means you need to add ai to all edges on the path from vi to ui. If ti = 2, it is followed by two integers vi and ki (1 ≤ vi ≤ n, 1 ≤ ki ≤ n) and means you need to find the sum of weights of all edges for which both endpoints are at distance at most ki form node vi. It is guaranteed that the number of queries of the first type will not be greater than 500.

Output

For each query of the second type, print exactly one integer on a separate line: the answer to the query.