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