// クラスカルのアルゴリズム　最小全域木の作成
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>

#include<queue>

using namespace std;

#define MAX 10000
#define INFTY (1 << 29)

// Union-Find木, Union-Findデータ構造のクラス
class DisjointSet
{
    public:
        // 木の高さ
        // 各ノード x を根とした時の木の高さが rank[x] となる
        vector<int> rank;
        // 親のNo.
        vector<int> p;

        // コンストラクタ
        DisjointSet() {}
        DisjointSet(int size)
        {
            rank.resize(size, 0);
            p.resize(size, 0);

            for(int i = 0; i < size; i++)
            {
                // 要素が 1つの集合を作る
                makeSet(i);
            }
        }

        // 要素が x ただ1つである新しい集合を作る
        void makeSet(int x)
        {
            // 根は自分自身を指すようにする
            p[x] = x;
            // 要素が 1 つの時は, rankは 0 とする
            rank[x] = 0;
        }

        // x と y が同じ集合に属するかの判定
        bool same(int x, int y)
        {
            return findSet(x) == findSet(y);
        }

        // 指定された2つの要素x, yを合併する
        void unite(int x, int y)
        {
            link(findSet(x), findSet(y));
        }

        // 2つの木を併合する処理
        void link(int x, int y)
        {
            // 低い木を高い木に合併する
            if( rank[x] > rank[y] )
            {
                p[y] = x;
            }
            else
            {
                p[x] = y;

                if( rank[x] == rank[y] )
                {
                    // 併合する木の高さが同じ時は,
                    // 合併される側の木の高さを 1 だけ増やす
                    rank[y]++;
                }
            }
        }

        // 要素 x が属する集合の"代表"の要素を求める
        // ( 戻り値は, 指定要素が属する木の親のNo. )
        int findSet(int x)
        {
            if( x != p[x] )
            {
                // ----------------
                // 経路圧縮を実施する
                // ----------------
                p[x] = findSet(p[x]);
            }

            // 根の値を返す ( x == p[x]の時は, 根である )
            return p[x];
        }
};

// 各辺の情報を持つクラス
class Edge
{
    public:
        // source : 辺の開始頂点, target : 辺の終了頂点, cost : 辺の重み
        int source, target, cost;

        Edge(int source = 0, int target = 0, int cost = 0) :
        source(source), target(target), cost(cost){ }

        // 演算子のオーバーロード ( sort()で使用 )
        bool operator < ( const Edge &e ) const
        {
            // costをキーにして並べ替える
            return cost < e.cost;
        }
};

// クラスカルのアルゴリズムを実施する関数
int kruskal(int N, vector<Edge> edges)
{
    int totalCost = 0;

    // 辺のcostの昇順に並び替える
    sort(edges.begin(), edges.end());

    DisjointSet dset = DisjointSet(N + 1);

    for(int i = 0; i < N; i++)
    {
        // 各頂点のみの要素が 1つの集合を作る
        dset.makeSet(i);
    }

    //int source, target;

    for(int i = 0; i < edges.size(); i++)
    {
        Edge e = edges[i];

        // 辺の始点と終点の頂点が、同じ集合に属しているかを調べる
        if( !dset.same(e.source, e.target) )
        {
            // 辺のコストの和を求める
            totalCost += e.cost;
            // 頂点を併合して, 最小全域木を作成する
            dset.unite(e.source, e.target);
        }
    }

    return totalCost;
}

int main(void)
{

    int N, M, cost;
    int source, target;

    cin >> N >> M;

    vector<Edge> edges;

    for(int i = 0; i < M; i++)
    {
        cin >> source >> target >> cost;
        edges.push_back( Edge(source, target, cost) );
    }

    cout << kruskal(N, edges) << endl;

    return 0;
}



Measured memory_bytes: 5396