Minimum Graph Traversal Cost

You are given an undirected graph with \(N\) nodes and \(M\) edges. Each edge has an associated weight. Your task is to compute the minimum cost required to traverse the graph such that every node is visited at least once. This problem can be solved by computing a Minimum Spanning Tree (MST) of the graph using Prim's algorithm.

Note: It is assumed that the graph is connected unless specified otherwise.

inputFormat

The input begins with a single line containing two integers \(N\) (number of nodes) and \(M\) (number of edges). The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\), indicating that there is an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer: the minimum cost to traverse the entire graph by visiting each node at least once (i.e. the sum of weights of the MST).

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

9