eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Автобусы и самолеты

Автобусы и самолеты

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

В Неверляндии имеется N городов, между которыми курсируют автобусы. Сверх того, между некоторыми городами действует воздушное сообщение (авиарейсы).

Каждый рейс (как автобусный, так и авиа) связывает два города (в обе стороны). Между любыми двумя городами проложено не более чем по одному рейсу каждого из типов. Продолжительность каждого из рейсов известна и одинакова в обе стороны.

Расписание рейсов идеально подогнано по времени, так что затраты времени на любой составной маршрут (состоящий из нескольких рейсов) равны просто сумме продолжительностей входящих в него отдельных рейсов.

В начальный момент времени Вы находитесь в городе А. Ваша задача – как можно быстрее попасть в город В. К сожалению, Вы ограничены в средствах, поэтому можете позволить себе не более М билетов на самолет (т.е. не более М раз можете воспользоваться авиарейсами).

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

Первая строка содержит числа N, M, A, B, разделенные пробелами (A и B – номера начального и конечного городов соответственно) (1N1000, 0M10, 1AN, 1BN, AB).

Вторая строка содержит V – количество автобусных рейсов (1V20000). Каждая из последующих V строк содержат описание одного рейса в следующем виде:

IJK (через 1 пробел), где I и J – номера городов, связанных этим рейсом, K – его продолжительность (в часах) (1IN, 1JN, IJ, 1K1000).

Следующая строка содержит W – количество авиарейсов (1W20000). Каждая из последующих W строк содержат описание одного авиарейса (так же, как и для автобусных рейсов).

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

Продолжительность кратчайшего маршрута (в часах) либо 0, если попасть в город B невозможно.

Пример

Входные данные #1
4 1 1 4
4
1 2 20
2 3 10
3 4 5
1 3 25
3
2 1 3
2 4 2
3 4 1
Выходные данные #1
18