Фрида работает в 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 строк описывают дополнительные рейсы в том же формате как и основные. Между одной парой городов может существовать более одного рейса. Считайте, что можно написать все отзывы, используя некоторые дополнительные рейсы.

Выходные данные

Вывести наименьшую общую стоимость билетов, которую Фрида должна заплатить чтобы совершить все обзоры и вернуться домой в Стокгольм.