Minimum Cost to Connect Planets

You are given an undirected weighted graph representing a network of planets. Each planet is a node and each edge represents a bidirectional route between two planets with an associated travel cost. Your task is to compute the minimum total cost required to connect all the planets, i.e. find the cost of a Minimum Spanning Tree (MST) of the graph.

Formally, you are given two integers \(N\) and \(M\) where \(N\) is the number of planets and \(M\) is the number of connections. Then, you are given \(M\) lines each containing three integers \(a\), \(b\) and \(c\) indicating a bidirectional edge between planet \(a\) and planet \(b\) with a cost of \(c\). The answer is the sum of the weights of the \(N-1\) edges chosen in the MST.

You can assume that the given graph is connected so an MST always exists. Use any efficient algorithm such as Kruskal's or Prim's algorithm.

inputFormat

The first line of the input contains two integers \(N\) and \(M\) separated by a space, denoting the number of planets and the number of connections respectively.

This is followed by \(M\) lines, each containing three integers \(a\), \(b\), and \(c\) representing a connection between planet \(a\) and planet \(b\) with cost \(c\). Planets are numbered from 1 to \(N\).

outputFormat

Output a single integer, which is the minimum total cost required to connect all the planets.

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

45