Мандри

Армія Речі Посполитої рухається з міста Кострома до села Домніно. Очолюють армію два гетьмани — Стефан і Костянтин.

Стефан придбав карту Костромської області, і кожної ночі він веде армію від одного села до іншого по одній із зазначених доріг. Костянтин же роздобув карту секретних стежок, і кожного дня він веде армію по одній із цих стежок. Перед кожним переходом кожен із гетьманів запитує у провідника Івана Сусаніна, який маршрут краще обрати.

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

Іван Сусанін, будучи таємним агентом, не хоче розкрити себе. Тому кожного разу він обирає дорогу (для Стефана) і стежку (для Костянтина) так, щоб найкоротша відстань до села Домніно, згідно з картою того гетьмана, який ставить питання, строго зменшувалася.

Допоможіть Івану знайти найдовший можливий шлях до села Домніно.

Вхідні дані

Перша строка містить три цілих числа $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$".

Приклади