Дано взвешенное дерево. Найти кратчайшее расстояние между заданными вершинами.

Первая строка содержит целое число n — количество вершин в дереве (1 ≤ n ≤ 50000). Вершины нумеруются целыми числами от 0 до n – 1. В следующих n – 1 строках содержится по три целых числа u, v, w, которые соответствуют ребру весом w (0 ≤ w ≤ 1000), соединяющему вершины u и v. В следующей строке содержится целое число m — количество запросов (1 ≤ m ≤ 75000). В следующих m строках содержится по два числа — номера вершин, расстояние между которыми необходимо вычислить.

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