Автобуси і літаки#668
У Неверляндії є міст, між якими курсують автобуси. Крім того, між деякими містами діє повітряне сполучення (авіарейси).
Кожен маршрут (автобусний чи авіа) з'єднує два міста в обидва боки. Між будь-якою парою міст може бути не більше одного маршруту кожного типу. Тривалість кожного маршруту відома і однакова в обох напрямках.
Розклади ідеально узгоджені у часі, тому загальний час для будь-якого складного маршруту (який складається з кількох ділянок) дорівнює просто сумі тривалостей складових маршрутів цього шляху.
Спочатку ви перебуваєте в місті . Ваша мета — якнайшвидше потрапити у місто . На жаль, ваші ресурси обмежені, ви можете придбати не більше квитків на літак (тобто скористатися авіарейсами не більше разів).
У першому рядку задано числа , , , , розділені пробілами ( та — номери початкового і кінцевого міст відповідно) (1 \leq N \leq 1000, 0 \leq M \leq 10, 1 \leq A \leq N, 1 \leq B \leq N, A \neq B).
Другий рядок містить — кількість автобусних маршрутів (1 \leq V \leq 20000). Кожен із наступних рядків містить опис одного маршруту у форматі:
(через пробіл), де та — номери міст, з'єднаних цим маршрутом, — його тривалість (у годинах) (1 \leq I \leq N, 1 \leq J \leq N, I \neq J, 1 \leq K \leq 1000).
Наступний рядок містить — кількість авіарейсів (1 \leq W \leq 20000). Кожен із наступних рядків містить опис одного авіарейсу (у тому ж форматі, що й для автобусних маршрутів).
Виведіть тривалість (у годинах) найкоротшого можливого маршруту або , якщо потрапити у місто неможливо.
Приклад 1