Вам дан ориентированный взвешенный граф из n вершин и 2n - 2 ребер. Вершины пронумерованы от 1 до n, а ребра пронумерованы от 1 до 2n - 2. Ребра графа могут быть разделены на две группы.
Вам дано q запросов. Есть два типа запросов
По данным запросам выведите длины кратчайших путей.
Первая строка содержит два целых числа n, q (2 ≤ n, q ≤ 200 000) — количество вершин и количество запросов, соответственно.
Каждая из следующих 2n - 2 строк содержит три целых числа ai, bi, ci, обозначаищие ребро от вершины ai до вершины bi с весом ci.
Первые n - 1 из этих строк описывают корневое основное дерево, направленное от вершины 1, а для оставшихся n - 1 строк будет выполняться bi = 1.
Детальнее,
Следующие 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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач