Problem Description

Given a map with several cities, where some cities may be connected by routes. We represent this using an undirected graph, where each edge has a weight indicating the cost to choose that edge. Given 4 pairs of vertices (which may be duplicates), find a set of edges with the minimum total weight such that any pair of vertices can be connected by the chosen edges.

Input Format

The first line contains two integers, \( n \) and \( m \), representing the number of cities and the number of edges, respectively.

The next \( n \) lines each contain a string, representing the name of each city. The city name is a string of no more than 20 lowercase letters.

The following \( m \) lines each provide \( s_1, s_2, w \), where \( s_1 \) and \( s_2 \) are the names of the cities, and \( w \) is the weight of the edge between them.

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

Output Format

Output a single line containing the minimum cost.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3907

Sample Input #2

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

Sample Output #2

10

Notes

The data guarantees that \( 1 \leq n \leq 30 \), \( 0 \leq m \leq 1000 \), and \( 1 \leq w \leq 10000 \).

见题面 Input 部分

见题面 Output 部分