В Неверляндии имеется 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 невозможно.