Вам дан ориентированный взвешенный граф из 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.
По данным запросам выведите длины кратчайших путей.
Выходные данные
Для каждого запроса второго типа, выведите длину кратчайшего пути на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|