E. Аварийная дорога
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В королевстве $$$n$$$ городов, связанных между собой двусторонними дорогами. Система дорог устроена так, что можно из любого города добраться до любого другого, а всего дорог $$$n - 1$$$.

Также есть два самых важных города — $$$s$$$ и $$$t$$$. Поэтому служба безопасности заранее просчитывает варианты дополнительных дорог на случай, если на одной из существующих произойдет авария, то есть проезд по данной дороге будет заблокирован.

Вас просят помочь службе безопасности и ответить на $$$q$$$ независимых запросов — какой будет кратчайший путь между городами $$$s$$$ и $$$t$$$, если произойдет авария на дороге между городами $$$a_1$$$ и $$$b_1$$$ и построят дополнительную дорогу между городами $$$a_2$$$ и $$$b_2$$$, длина которой будет равна $$$c$$$.

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

В первой строке заданы три числа $$$n, s, t$$$ — количество городов и номера двух самых важных городов $$$(2 \leq n \leq 2 \cdot 10^5, 1 \leq s, t \leq n, s \neq t)$$$.

В следующих $$$n - 1$$$ строках заданы описания дорог $$$u_i, v_i, w_i$$$ — дорога между городами $$$u_i$$$ и $$$v_i$$$, длина которой равна $$$w_i$$$ $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq w_i \leq 10^9)$$$.

В следующей строке задано одно число $$$q$$$ — количество запросов $$$(1 \leq q \leq 2 \cdot 10^5)$$$.

В следующих $$$q$$$ строках задано описание каждого запроса пятью числами $$$a_1, b_1, a_2, b_2, c$$$ — авария на дороге между городами $$$a_1$$$ и $$$b_1$$$, и новая дорога между городами $$$a_2$$$ и $$$b_2$$$, длина которой равна $$$c$$$ $$$(1 \leq a_1, b_1, a_2, b_2 \leq n, a_1 \neq b_1, a_2 \neq b_2, 1 \leq c \leq 10^9)$$$.

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

Для каждого из $$$q$$$ запросов выведите по одному числу на новой строке — минимальное расстояние между городами $$$s$$$ и $$$t$$$. Если пути между городами не существует, то выведите $$$-1$$$.

Система оценки
ГруппаБаллыДоп. ограниченияСистема оценки
$$$0$$$$$$0$$$—Тесты из условия
$$$1$$$$$$10$$$$$$n \leq 100, w_i \leq 100, q = 1$$$Полная группа
$$$2$$$$$$12$$$$$$n, q \leq 10^3$$$Полная группа
$$$3$$$$$$10$$$$$$a_1 = a_2, b_1 = b_2, q = 1$$$Полная группа
$$$4$$$$$$12$$$$$$a_1 = a_2, b_1 = b_2$$$Полная группа
$$$5$$$$$$16$$$$$$u_i = i, v_i = i + 1,s = 1, t = n$$$Полная группа
$$$6$$$$$$40$$$—Полная группа
Пример
Входные данные
6 1 2
1 3 10
3 2 6
4 2 1
4 5 2
6 2 13
3
1 3 2 1 10
1 3 3 1 5
2 6 4 1 1
Выходные данные
10
11
2