Путешествие

Армия Речи Посполитой движется из города Костромы в деревню Домнино. Во главе армии стоят два гетмана – Стефан и Константин.

Стефан приобрел карту Костромской области, и каждую ночь он ведет армию от одной деревни к другой по одной из указанных дорог. Константин же раздобыл карту секретных троп, и каждый день он ведет армию по одной из этих троп. Перед каждым переходом каждый из гетманов спрашивает у проводника Ивана Сусанина, какой маршрут лучше выбрать.

На карте у Стефана указана длина каждой дороги, поэтому он знает минимальные расстояния между любой деревней и деревней Домнино по своей карте. Аналогично, Константин знает кратчайшие расстояния до Домнино, если следовать по тропам согласно его карте.

Иван Сусанин, будучи тайным агентом, не хочет разоблачить себя. Поэтому каждый раз он выбирает дорогу (для Стефана) и тропу (для Константина) так, чтобы кратчайшее расстояние до деревни Домнино, согласно карте того гетмана, который задает вопрос, строго уменьшалось.

Помогите Ивану найти самый длинный возможный путь до деревни Домнино.

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

Первая строка содержит три целых числа $n,s$ и $t(2\le n\le 1000,1\le s,t\le n)$ — количество деревень в Костромской области, а также номера начальной деревни и деревни Домнино. Деревни пронумерованы числами от $1$ до $n$. Начальная деревня и деревня Домнино различны.

Далее следуют два блока, каждый из которых задает карту: первый блок — карту Стефана, второй — карту Константина.

Первая строка каждого блока содержит целое число $m(n-1\le m\le 10^5)$ — количество дорог/троп между деревнями. Каждая из следующих $m$ строк содержит три целых числа $a,b$ и $l$, описывающих дорогу или тропу между деревнями $a$ и $b$ длиной $l(1\le a,b\le n;1\le l\le 10^6)$.

Армия может двигаться в любом направлении по дорогам и тропам. Известно, что по карте каждого гетмана можно добраться из любой деревни в любую. Армия стартует вечером из начальной деревни, продвигаясь по одной дороге каждую ночь и по одной тропе каждый день.

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

Выведите длину самого длинного пути, по которому Иван Сусанин может водить армию Речи Посполитой, пока она не достигнет деревни Домнино (с учетом дорог и троп). Если Иван может водить армию бесконечно, не достигая Домнино, выведите "$-1$".

Примеры