Problem Description

You are given a map with some cities. There may be routes connecting cities. To simplify, we use an undirected graph: each edge has a weight, meaning the cost to choose this edge. Given $4$ pairs of vertices (pairs may repeat), find a set of edges with the minimum total weight such that every given pair of vertices is connected using only the chosen edges.

Input Format

The first line contains $2$ integers, $n$ and $m$, which represent the number of cities and the number of edges.

The next $n$ lines each contain a string, the name of a city. Each city name is a string of lowercase letters of length at most $20$.

The next $m$ lines each contain $s_1, s_2, w$, where $s_1$ and $s_2$ are city names, and $w$ is the weight of the edge between them.

Finally, there are $4$ lines, each containing two strings, which are the names of a required pair of cities.

Output Format

Output one line containing the minimum cost.

10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki

3907

2 1
first
second
first second 10
first first
first first
second first
first first

10

Hint

Constraints: $1\leq n\leq 30$, $0\leq m\leq 1000$, $1\leq w\leq 10000$.

Translated by ChatGPT 5