Огляд продуктів харчування
Фріда працює в Cosmopolitan і пише огляди ресторанів. Вона любить свою роботу, але здається, що за багато років вона вже відвідала всі ресторани на Землі. Тепер настав час піднятися на новий рівень; вона планує написати огляд харчування, яке подають авіакомпанії, щоб читачі могли приймати більш обґрунтовані рішення про свої польоти.
Бос Фріди надав їй список авіарейсів, які вона повинна розглянути в наступному випуску Cosmopolitan. Вона знає, що однакова їжа подається в обох напрямках кожного польоту, тому кожен рейс достатньо перевірити лише один раз. Вона також зрозуміла, що їй слід скористатися деякими додатковими рейсами, оскільки вона не зможе зробити всі відгуки, використовуючи лише рейси зі списку свого боса. Тому вона провела кілька швидких досліджень і склала список додаткових рейсів, які вона може використовувати. Фріда не буде вивчати їжу на цих рейсах; вони будуть використовуватися лише для того, щоб вона змогла зробити всі необхідні відгуки.
Мета Фріди - зробити всі огляди, витративши при цьому мінімум грошей на квитки на літак. Її офіс знаходиться в Стокгольмі, тому вона починає і закінчує подорож саме там. Кожен політ між двома містами має фіксовану ціну в обох напрямках. Відомо, що можна написати всі відгуки, використовуючи деякі додаткові рейси.
У цій задачі ми будемо ігнорувати витрати на проживання, а також час вильоту і прибуття рейсів, вважаючи, що польоти виконуються досить часто і в короткий час. Нас цікавить лише мінімізація загальної вартості польотів.
Вхідні дані
Перша стрічка містить два цілі числа 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 задають два різних аеропорти, а c - вартість польоту в шведських кронах в обох напрямках. Жодна пара з двох міст не представлена двічі.
Наступний рядок містить кількість допустимих додаткових рейсів f (0 ≤ f ≤ 200). Наступні f рядків описують додаткові рейси в тому ж форматі, як і основні. Між однією парою міст може існувати більше одного рейсу. Вважайте, що можна написати всі відгуки, використовуючи деякі додаткові рейси.
Вихідні дані
Виведіть найменшу загальну вартість квитків, яку Фріда повинна заплатити, щоб здійснити всі огляди і повернутися назад в Стокгольм.