Problem D
Spanning-USA

Emblem of the most famous road in USA. By Levente Jakab (public domain)

You are working on a project that will rebuild roads that connect major cities in USA with all other major cities. However, your supervisors have no idea how much asphalt is needed for this project. You know that they might be angry if you ask for too much asphalt. You need to find the minimal amount of asphalt needed to build a road network that connects all cities.

Also you know that even if this project is only for the US, you know that you could easily sell your program to other countries, for example Sweden. Therefore you’d like to write a general program that solves this for any collection of cities with possible roads to build.

Input

The first line contains integers $N$ and $M$, such that $1 \leq N \leq 128$ and $1 \leq M \leq 10\, 000$. Then follow $N$ lines each containing a unique city name. The next $M$ lines each contain a description of a road that is possible to build. To avoid ambiguities each city name consists only of characters from the set {a—z, A—Z}. Also, each city name has between $1$ and $20$ characters.

Each road description is on the following format: $a \ b \ l$, where $a$ and $b$ are names of the cities this road connects. The length of the road, $l$, is an integer such that $1 \leq l \leq 10\, 000$. The length corresponds excactly to how much asphalt you need to build that road.

There will be no two roads connecting the same cities $a$ and $b$. It is guaranteed that for every road $a \not= b$.

Output

Output the minimal amount of asphalt needed to build your road network. If it’s not possible to pick roads to form a graph connecting all cities, output $-1$.

4 6
NewYork
Miami
Seattle
LosAngeles
NewYork Miami 1277
NewYork Seattle 2852
NewYork LosAngeles 2790
Miami Seattle 3300
Miami LosAngeles 2747
Seattle LosAngeles 1135

5159

4 3
A
B
C
D
A B 1
A C 1
B C 1

-1