Problem 25: Road Construction

Problem Statement: A country plans to connect all its cities by constructing roads. Given a weighted undirected graph with n nodes and m edges, compute the minimum total cost required to connect all cities (i.e., find the cost of the minimum spanning tree).

Input

The first line contains two integers n and m. The next m lines each contain three integers u, v, and w representing an edge between u and v with weight w.

Output

Print the total cost of constructing the roads (MST cost).

Examples


Input:
4 5
1 2 1
2 3 2
3 4 3
4 1 4
2 4 1

Output:
4

Solution Explanation

Method 1: Use Kruskal's Algorithm by sorting all edges and adding them one by one if they connect separate components using union-find data structure. Method 2: Use Prim's Algorithm starting from any vertex and repeatedly adding the minimum cost edge that expands the tree.

Solution in C++


#include 
#include 
#include 
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

int findp(int a, vector& parent){
    return parent[a] == a ? a : parent[a] = findp(parent[a], parent);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector edges(m);
    for (int i = 0; i < m; i++){
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges.begin(), edges.end());
    vector parent(n+1);
    for(int i=1; i<=n; i++) parent[i]=i;
    long long cost = 0;
    for(auto &e : edges){
        int pu = findp(e.u, parent);
        int pv = findp(e.v, parent);
        if(pu != pv){
            cost += e.w;
            parent[pu] = pv;
        }
    }
    cout << cost << "
";
    return 0;
}