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