eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Автобуси і літаки

Автобуси і літаки

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

У Неверляндії є N міст, між якими курсують автобуси. Крім того, між деякими містами діє повітряне сполучення (авіарейси).

Кожен рейс (як автобусний, так і авіа) зв'язує два міста (в обидві сторони). Між довільними двома містами прокладено не більше ніж по одному рейсу кожного з типів. Тривалість кожного з рейсів відома і однакова в обидві сторони.

Раклад рейсів ідеально підігнано по часу, так що затрати часу на довільний складний маршрут (що складається з декількох рейсів) рівні просто сумі тривалостей окремих рейсів, що входять до нього.

У початковий момент часу Ви знаходитесь у місті А. Ваше завдання – якомога швидше попасти в місто В. На жаль, Ви обмежені у коштах, тому можете дозволити собі не більше М квитків на літак (тобто не більше М разів можете скористатись авіарейсами).

Вхідні дані

Перший рядок містить числа N, M, A, B, відокремлені пропусками (A та B – номери початкового і кінцевого міст відповідно) (1N1000, 0M10, 1AN, 1BN, AB).

Другий рядок містить V – кількість автобусних рейсів (1V20000). Кожен з наступних V рядків містить опис одного рейсу у наступному виді:

IJK (через 1 пропуск), де I та J – номери міст, зв'язаних цим рейсом, K – його тривалість (в годинах) (1IN, 1JN, IJ, 1K1000).

Наступний рядок містить W – кількість авіарейсів (1W20000). Кожен з наступних W рядків містить опис одного авіарейсу (так само, як і для автобусних рейсів).

Вихідні дані

Тривалість найкоротшого маршруту (в годинах) або 0, якщо попасти в місто B неможливо.

Приклад

Вхідні дані #1
4 1 1 4
4
1 2 20
2 3 10
3 4 5
1 3 25
3
2 1 3
2 4 2
3 4 1
Вихідні дані #1
18