Minimal Cost to Connect Cities

You are given an undirected weighted graph representing a network of cities and roads. The cities are numbered from 1 to \(n\), where city 1 is the capital. Each road connects two cities \(u\) and \(v\) with a certain cost \(w\). Your task is to compute the minimum total cost to connect all the cities, ensuring that there exists a path from the capital (city 1) to every other city.

This problem can be solved using the Minimum Spanning Tree (MST) approach. In particular, you can use Prim's algorithm which constructs the MST starting from the capital. The total cost is given by: $$\sum_{e \in MST} w_e$$ where \(w_e\) is the cost of an edge in the MST.

inputFormat

The input is read from stdin. The first line contains two integers \(n\) and \(m\), representing the number of cities and roads respectively. Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\), indicating that there is a road between city \(u\) and city \(v\) with cost \(w\>.

outputFormat

Output a single integer to stdout — the minimal total cost required to connect all the cities so that every city is reachable from the capital (city 1).

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

11