Minimum Cost to Supply Electricity

In this problem, you are given N power plants and M cities together with K possible connections. Each connection is represented as a triple ( (u, v, w) ) where u is the index of a power plant, v is the index of a city (both 1-indexed), and w is the cost to supply electricity from that power plant to that city. For each city, you must choose a connection with the minimum cost available. If any city cannot be connected to any power plant, output -1. Otherwise, output the sum of these minimum costs.

Note: All formulas are represented in LaTeX, e.g. ( (u, v, w) ).

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains three integers: N, M, and K, where N is the number of power plants, M is the number of cities, and K is the number of available connections.
• Each of the next K lines contains three integers: u, v, and w, indicating a connection from power plant u to city v with a cost of w.

outputFormat

Output a single integer representing the minimum total cost to supply electricity to all the cities. If it is impossible to supply electricity to every city (i.e. at least one city is left unconnected), output -1.## sample

2 3 4
1 1 10
1 2 15
2 2 20
2 3 30

55