Автобуси і літаки
У Неверляндії є 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 неможливо.