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