Билет на поезд
"Ticket to Ride" — это настольная игра для 5 игроков. Цель игры — строить железнодорожные линии и мешать соперникам делать то же самое. В начале игры каждому игроку назначаются четыре железнодорожные линии. Игрок может выбрать, сколько из этих четырех заданий он хочет сбросить. Каждое задание имеет оценку, отражающую его сложность (например, железнодорожная линия между Стокгольмом и Токио будет стоить больше, чем линия между Стокгольмом и Утрехтом). В конце игры игроки получают очки за выполненные задания и штрафные очки за невыполненные.
Задание состоит из пары городов, которые нужно соединить серией более коротких железнодорожных маршрутов. Маршрут можно занять за определенную стоимость, но сложность в том, что маршрутов ограниченное количество, и как только один игрок занимает маршрут, другие игроки не могут его использовать. Игрок успешно прокладывает железнодорожную линию между двумя городами, если существует путь между этими городами, используя только маршруты, занятые этим игроком. Для простоты мы будем игнорировать все дополнительные аспекты игры, включая процесс занятия маршрутов и дополнительные способы набора очков.
Например, если ваше задание — соединить Стокгольм и Амстердам на рисунке выше, вы, вероятно, захотите занять маршруты между Стокгольмом и Копенгагеном, а также между Копенгагеном и Амстердамом. Но если другой игрок успеет занять маршрут между Копенгагеном и Стокгольмом раньше вас, ваша железнодорожная линия должна будет использовать другие маршруты, например, через Осло.
В этой задаче мы рассмотрим стратегию выполнения всех четырех заданий, что обычно довольно сложно. Чтобы предварительно оценить сложность этой задачи, мы хотим рассчитать минимальную стоимость прокладки всех четырех линий, предполагая, что другие игроки не мешают нашим планам. Ваша задача — написать программу, определяющую эту минимальную стоимость.
Входные данные
Входные данные состоят из нескольких (не более 20) игр для анализа. Каждая игра начинается с двух целых чисел 1 ≤ n ≤ 30, 0 ≤ m ≤ 1000, которые задают количество городов и железнодорожных маршрутов на карте соответственно. Далее следуют n строк с названиями n городов. Названия городов имеют длину не более 20 символов и состоят только из строчных букв ('a'-'z').
Затем следуют m строк, каждая из которых содержит названия двух разных городов и целое число 1 ≤ c ≤ 10000, указывающее, что существует железнодорожный маршрут с стоимостью c между этими двумя городами. Обратите внимание, что может быть несколько маршрутов между одной и той же парой городов. Вы можете предположить, что всегда возможно проложить железнодорожную линию из любого города в любой другой город.
Наконец, будут даны четыре строки, каждая из которых содержит названия двух городов, задающих четыре задания на железнодорожные линии.
Входные данные завершаются случаем, когда n = m = 0. Этот случай не должен обрабатываться.
Выходные данные
Для каждой игры выведите одну строку, содержащую одно целое число — минимально возможную стоимость прокладки всех четырех железнодорожных линий.