Minimum Travel Cost

You are given a network of cities connected by roads, where each road connects two cities and has an associated travel cost. Your task is to compute the minimum total cost required to connect all the cities (i.e., build a minimum spanning tree). If it is impossible to connect all the cities, output -1.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

The road network is described by an integer n on the first line representing the number of roads, followed by n lines each containing two city names and an integer cost separated by spaces. City names are strings without spaces.

The minimum spanning tree cost is the sum of the costs of the selected roads such that every city is reachable from every other city. If some cities cannot be connected, return -1.

The formula for the MST cost using a union-find (or any MST algorithm) approach can be written as:

\( TotalCost = \sum_{e \in MST} cost(e) \)

inputFormat

The input is read from stdin with the following format:

N
city1 city2 cost
city1 city2 cost
... (N lines total)

Where N is the number of roads. Each road is represented by two strings (city names) and an integer cost.

outputFormat

Output a single integer, which is the minimum travel cost to connect all the cities. If it is impossible to connect all the cities, output -1.

## sample

3
A B 1
B C 2
A C 4

3

</p>