Побег Майлза
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Майлз опять сбегает от Мигеля О'Хары, но в этот раз он смог захватить с собой устройство для перемещения между двумя мирами. К сожалению, его перемещения ограничены одним городом в каждом из миров. Но эти два города очень похожи: в каждом из них ровно $$$n$$$ небоскребов, располагающихся в одних и тех же точках пространства.

Некоторые пары небоскребов, расположенных в одном мире, пригодны для того, чтобы протянуть между ними паутину и переместиться с одного на другой (в любом из двух направлений). В первом мире есть ровно $$$m_1$$$ таких пар небоскребов, а во втором — ровно $$$m_2$$$. Известно, за какое время можно переместиться между доступными парами небоскребов в каждом мире. Помимо этого Майлз может, находясь на $$$i$$$-м небоскребе в первом мире, переместиться на $$$i$$$-й небоскреб во втором, и наоборот, за $$$x$$$ секунд.

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

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

Первая строка ввода содержит два целых числа $$$n$$$ и $$$x$$$ — количество небоскребов в каждом из двух миров и время перемещения между соответствующими небоскребами разных миров ($$$1 \le n \le 10^5$$$; $$$1 \le x \le 10^6$$$).

Вторая строка содержит число $$$m_1$$$ — количество пар небоскребов, между которыми можно перемещаться в городе первого мира ($$$0 \le m_1 \le 10^6$$$).

Следующие $$$m_1$$$ строк содержат по три числа $$$u_i$$$, $$$v_i$$$ и $$$c_i$$$, означающих, что между небоскребами $$$u_i$$$ и $$$v_i$$$ в первом мире можно переместиться в любом направлении за $$$c_i$$$ секунд ($$$1 \le u_i, v_i \le n$$$; $$$1 \le c_i \le 10^6$$$).

В следующих строках в таком же формате содержится информация о возможных перемещениях между небоскребами второго мира: в первой из этих строк дано число $$$m_2$$$, а следующие $$$m_2$$$ строк содержат сами описания перемещений (в виде троек чисел $$$u_i$$$, $$$v_i$$$ и $$$c_i$$$).

Последняя строка содержит два целых числа $$$s$$$ и $$$t$$$ — номер стартового небоскреба в первом мире и конечного во втором ($$$1 \le s, t \le n$$$).

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

Выведите единственное целое число — минимальное время путешествия между небоскребом $$$s$$$ первого мира и небоскребом $$$t$$$ второго мира, или -1, если между ними нет пути.

Пример

Входные данные
6 2
7
1 3 2
6 4 1
4 1 5
5 3 2
1 2 1
1 5 4
2 3 4
6
4 2 1
2 1 5
5 2 3
3 1 5
1 5 4
2 6 1
5 6
Выходные данные
6