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 in C++


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int findp(int a, vector<int>& 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<Edge> 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<int> 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 << "\n";
    return 0;
}