У Неверляндії є \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} неможливо.