Задано неориентированное дерево с n вершинами, ребрам которого присвоены веса. Необходимо выполнить запросы двух типов:

1. Прибавить значение ai ко всем ребрам на пути от вершины vi до вершины ui. Этого типа имеется не более 500 запросов.
2. Вычислить сумму весов всех ребер, оба конца которых находятся на расстоянии не более ki от vi. Расстояние между двумя вершинами равно числу ребер на пути между ними.

Выполнять запросы следует в указанном порядке. Для каждого запроса второго типа вывести найденное значение.

Входные данные

Первая строка содержит два числа n и q (1 ≤ n ≤ 1000, 0 ≤ q ≤ 500000) - количество вершин в дереве и количество запросов. Следующая n - 1 строка содержит описание дерева: i-ая строка содержит три числа vi, ui и wi (1 ≤ vi, ui ≤ n, 1 ≤ wi ≤ 100000) - номера вершин, соединенных ребром, и его вес. Гарантируется, что граф является деревом.

Следующие q строк описывают запросы. В этих строках первым числом ti является тип запроса (1 ≤ ti ≤ 2). Если ti = 1, то далее следуют три числа vi, ui и ai (1 ≤ vi, ui ≤ n, 1 ≤ ai ≤ 100000), означающих что надо добавить ai ко всем ребрам на пути от vi до ui. Если ti = 2, то далее следуют два числа vi и ki (1 ≤ vi ≤ n, 1 ≤ ki ≤ n), означающих что надо найти сумму весов всех ребер, концы которых находятся на расстоянии не больше ki от вершины vi. Гарантируется, что запросов первого типа не более 500.

Выходные данные

Для каждого запроса второго типа вывести в отдельной строке ответ на него.