Minimum Magical Energy for Cross-Pollination

You are given n flower beds labeled from 1 to n and m magical connections available between them. Each magical connection is described by three integers a, b, and c, where a and b denote the flower beds and c denotes the energy cost to connect them. Your task is to determine the minimum magical energy required to ensure that all flower beds can be cross-pollinated, i.e. they all become connected in one network. If it is impossible to connect all flower beds using the available connections, output -1.

This problem can be modeled as finding the minimum spanning tree (MST) of an undirected weighted graph. The solution is based on Kruskal's algorithm. Recall that a spanning tree for a connected graph is a subgraph that is a tree and connects all the vertices. The total cost of the spanning tree is the sum of the weights of its edges. In LaTeX, you can express this as:

\(\text{Total Cost} = \sum_{e \in T} c_e\), where \(T\) is the set of edges in the MST.

inputFormat

The first line of input contains two integers n and m, where n is the number of flower beds and m is the number of magical connections available.

Each of the next m lines contains three space-separated integers a, b, and c representing a connection between flower beds a and b with an energy cost of c.

outputFormat

Output a single integer representing the minimum magical energy required to connect all flower beds. If it is impossible to connect all flower beds, output -1.

4 5
1 2 3
2 3 4
3 4 2
4 1 6
1 3 5

9