B. Расходящиеся направления
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан ориентированный взвешенный граф из n вершин и 2n - 2 ребер. Вершины пронумерованы от 1 до n, а ребра пронумерованы от 1 до 2n - 2. Ребра графа могут быть разделены на две группы.

  • Первые n - 1 ребер образуют корневое основное дерево, вершина 1 является корнем. Все ребра направлены от корня.
  • Последние n - 1 ребер идут от i к 1, для всех 2 ≤ i ≤ n.

Вам дано q запросов. Есть два типа запросов

  • 1 i w: Изменить вес i-го ребра на w;
  • 2 u v: Вывести длину кратчайшего пути между вершинами u и v.

По данным запросам выведите длины кратчайших путей.

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

Первая строка содержит два целых числа n, q (2 ≤ n, q ≤ 200 000) — количество вершин и количество запросов, соответственно.

Каждая из следующих 2n - 2 строк содержит три целых числа ai, bi, ci, обозначаищие ребро от вершины ai до вершины bi с весом ci.

Первые n - 1 из этих строк описывают корневое основное дерево, направленное от вершины 1, а для оставшихся n - 1 строк будет выполняться bi = 1.

Детальнее,

  • Ребра (a1, b1), (a2, b2), ... (an - 1, bn - 1) описывают корневое основное дерево, каждое из ребер которого направлено в сторону от вершины 1.
  • bj = 1 for n ≤ j ≤ 2n - 2.
  • an, an + 1, ..., a2n - 2 — различные целые числа от 2 до n.

Следующие q строк содержат по три целых числа каждая, описывающие запрос в формате, описанном в условии.

Все веса ребер будут в пределах от 1 до 106.

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

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

Пример
Входные данные
5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4
Выходные данные
0
1
4
8
100
132
10