Обзор еды
Фрида — обозревательница ресторанов для Cosmopolitan. Она обожает свою работу, но кажется, что за эти годы она уже посетила все рестораны на Земле. Теперь она решила поднять планку и начать обозревать еду, которую подают в авиакомпаниях, чтобы помочь читателям выбирать рейсы с лучшим питанием.
Ее начальник предоставил ей список авиарейсов, которые она должна обозреть для следующего выпуска Cosmopolitan. Фрида знает, что на обоих направлениях каждого рейса подают одинаковую еду, поэтому ей достаточно взять рейс только в одном направлении. Однако, чтобы сделать все обзоры, ей придется воспользоваться дополнительными рейсами, так как рейсов из списка начальника недостаточно. Она провела исследование и составила список таких дополнительных рейсов. На этих рейсах она не будет обозревать еду; они нужны только для того, чтобы добраться до нужных мест. Цель Фриды — выполнить все обзоры, потратив как можно меньше денег на билеты. Ее путешествие начинается и заканчивается в Стокгольме. Каждый рейс является двусторонним между двумя городами и имеет фиксированную цену в обоих направлениях. Можно предположить, что все обзоры можно выполнить, используя некоторые из дополнительных рейсов.
Для этой задачи мы игнорируем стоимость проживания и время рейсов, предполагая, что каждый рейс выполняется часто и длится недолго. Мы сосредотачиваемся только на минимизации общей стоимости рейсов.
Входные данные
Входные данные содержат несколько тестовых случаев.
Каждый тестовый случай начинается с строки с двумя целыми числами N и R, (2 ≤ N ≤ 13, 0 ≤ R ≤ 78), где N — количество аэропортов, а R — количество рейсов для обзора. Аэропорты пронумерованы от 1 до N, и Стокгольм имеет номер 1.
Следующие R строк описывают рейсы для обзора. Каждая строка содержит три целых числа a, b, c (1 ≤ a, b ≤ N, 1 ≤ c ≤ 10000), где a и b — это два различных аэропорта, а c — стоимость рейса в шведских кронах в обоих направлениях. Ни одна пара городов не указана дважды.
Следующая строка содержит целое число F, (0 ≤ F ≤ 200), количество доступных дополнительных рейсов.
Следующие F строк описывают дополнительные рейсы в том же формате, что и выше. Между парой городов может быть несколько рейсов. Можно предположить, что все обзоры можно выполнить, используя некоторые из этих дополнительных рейсов.
Входные данные заканчиваются строкой "0 0".
Выходные данные
Для каждого тестового случая выведите одно целое число — минимальную общую стоимость билетов, чтобы Фрида могла выполнить все обзоры и вернуться в Стокгольм.