티켓 투 라이드

티켓 투 라이드는 최대 5명이 함께 즐기는 보드게임입니다. 목표는 자신의 기차 노선을 완성하고, 동시에 상대가 노선을 완성하지 못하도록 방해하는 것입니다. 게임을 시작할 때 각 플레이어에게는 네 개의 노선 과제가 주어집니다. 각 과제에는 난이도에 따른 점수가 매겨져 있으며(예를 들어 스톡홀름과 도쿄를 잇는 노선은 보통 스톡홀름과 위트레흐트를 잇는 노선보다 점수가 높습니다), 플레이어는 원하는 만큼 과제를 버릴 수 있습니다. 게임이 끝나면 완성한 과제에 대해서는 점수를, 완성하지 못한 과제에 대해서는 벌점을 받습니다.

하나의 과제는 여러 개의 짧은 철도 구간(route)을 이어서 연결해야 하는 두 도시로 이루어집니다. 각 구간은 정해진 비용을 내고 점유(claim)할 수 있지만, 구간의 수가 한정되어 있고 한 플레이어가 어떤 구간을 점유하면 다른 플레이어는 그 구간을 점유할 수 없습니다. 어떤 플레이어가 자신이 점유한 구간만으로 두 도시를 잇는 경로를 만들 수 있으면, 그 두 도시 사이의 노선을 성공적으로 완성한 것입니다. 문제를 단순화하기 위해 구간을 실제로 점유하는 과정이나 추가 점수 규칙 등 다른 요소는 모두 무시합니다.

예를 들어 스톡홀름과 암스테르담을 잇는 과제를 받았다면, 스톡홀름–코펜하겐 구간과 코펜하겐–암스테르담 구간을 점유하려 할 것입니다. 하지만 다른 플레이어가 코펜하겐–스톡홀름 구간을 먼저 점유해 버리면, 예컨대 오슬로를 거쳐 코펜하겐으로 가는 식으로 다른 구간을 이용해야 합니다.

이 문제에서는 네 개의 과제를 모두 완성하려는 다소 무모한 전략을 생각합니다. 이것이 얼마나 어려운지 미리 가늠해 보기 위해, 다른 플레이어가 전혀 방해하지 않는다고 가정하고 네 노선을 모두 구성하는 데 드는 최소 비용을 계산하려 합니다. 이 최소 비용을 구하는 프로그램을 작성하세요.

입력은 분석할 여러 개의 게임으로 구성됩니다(최대 20개). 각 게임은 두 정수 $1 \le n \le 30$, $0 \le m \le 1000$ 으로 시작하며, 각각 지도의 도시 수와 철도 구간 수를 뜻합니다. 이어서 $n$개의 줄에 도시 이름이 하나씩 주어집니다. 도시 이름은 최대 20글자이고 소문자 알파벳('a'-'z')으로만 이루어집니다.

그 다음 $m$개의 줄에는 각각 서로 다른 두 도시의 이름과 정수 $1 \le c \le 10000$ 이 주어지며, 두 도시 사이에 비용 $c$인 철도 구간이 있음을 뜻합니다. 같은 두 도시 사이에 여러 개의 구간이 있을 수 있습니다. 어떤 도시에서든 다른 어떤 도시로도 노선을 구성할 수 있음이 항상 보장됩니다.

마지막으로 네 개의 줄에 각각 두 도시의 이름이 주어지며, 이것이 네 개의 노선 과제입니다.

입력은 $n = m = 0$ 인 게임으로 끝나며, 이 게임은 처리하지 않습니다.

각 게임마다 네 노선을 모두 구성하는 데 드는 최소 비용을 한 줄에 하나의 정수로 출력하세요.

티켓 투 라이드(Ticket to Ride)의 저작권은 Days of Wonder, Inc.에 있습니다.