Автобусы и самолеты
В Неверляндии имеется N городов, между которыми курсируют автобусы. Сверх того, между некоторыми городами действует воздушное сообщение (авиарейсы).
Каждый рейс (как автобусный, так и авиа) связывает два города (в обе стороны). Между любыми двумя городами проложено не более чем по одному рейсу каждого из типов. Продолжительность каждого из рейсов известна и одинакова в обе стороны.
Расписание рейсов идеально подогнано по времени, так что затраты времени на любой составной маршрут (состоящий из нескольких рейсов) равны просто сумме продолжительностей входящих в него отдельных рейсов.
В начальный момент времени Вы находитесь в городе А. Ваша задача – как можно быстрее попасть в город В. К сожалению, Вы ограничены в средствах, поэтому можете позволить себе не более М билетов на самолет (т.е. не более М раз можете воспользоваться авиарейсами).
Входные данные
Первая строка содержит числа N, M, A, B, разделенные пробелами (A и B – номера начального и конечного городов соответственно) (1 ≤ N ≤ 1000, 0 ≤ M ≤ 10, 1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B).
Вторая строка содержит V – количество автобусных рейсов (1 ≤ V ≤ 20000). Каждая из последующих V строк содержат описание одного рейса в следующем виде:
I J K (через 1 пробел), где I и J – номера городов, связанных этим рейсом, K – его продолжительность (в часах) (1 ≤ I ≤ N, 1 ≤ J ≤ N, I ≠ J, 1 ≤ K ≤ 1000).
Следующая строка содержит W – количество авиарейсов (1 ≤ W ≤ 20000). Каждая из последующих W строк содержат описание одного авиарейса (так же, как и для автобусных рейсов).
Выходные данные
Продолжительность кратчайшего маршрута (в часах) либо 0, если попасть в город B невозможно.