# Prim 演算法

graph G {
    node[shape=circle]
    {rank=same;0}
    {rank=same;1,2}
    {rank=same;3,4,5,6}
    0 -- 1 [label=3]
    0 -- 2 [label=1]
    1 -- 3 [label=1]
    1 -- 5 [label=1]
    2 -- 5 [label=7]
    2 -- 6 [label=5]
    3 -- 4 [label=2]
    4 -- 5 [label=1]
}

//
// Minimum Cost Spanning Tree - Prim
//
//  由單點的樹，挑選 n-1 條最小成本且不會造成 loop 的邊逐漸往外展開
//
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <queue>

using namespace std;

//---------------------------------------------------------------------------
// 測試資料
//
// 第一行，一個整數 n 表示有幾個節點
// 剩下一直到結尾的每一行的 3 個整數都代表一條邊，格式為 v1 v2 w
//  v1 v2 代表線的兩個端點，
//  w 代表這條線的權重(或成本)
//
string input = "\
7\n\
0 1 3\n\
0 2 1\n\
1 3 1\n\
1 5 1\n\
2 5 7\n\
2 6 5\n\
3 4 2\n\
4 5 1\n";
//---------------------------------------------------------------------------

// Prim 演算法是由已選中的樹中往外挑邊來展開，所以只記外連的端點就可以了
struct Edge {
    int to, weight;
};
// 重載 < 運算子，定義如何比較兩個 Edge 變數
// priority_queue<Edge> 會自動調用這個運算子，將優先權高的排在前面
bool operator<(const Edge &e1, const Edge &e2)
{
    // weight 高的優先權較小
    return e1.weight > e2.weight;
}

typedef vector<Edge>    Node;   // 每個節點記錄外連的邊
typedef vector<Node>    Graph;  // 用 vector 記錄圖的組態

int mst_prim(Graph g)
{
    vector<bool>    selected(g.size()); // 節點已經被選取了
    priority_queue<Edge>    pq;         // 目前的樹外連的邊
    int remain_edges = g.size(),        // 只要挑完 n-1 條邊就可以了(多第一條虛邊{0, 0})
        min_cost = 0;

    pq.push({0, 0});    // 第一條虛邊，成本為 0，不影響結果

    while (remain_edges > 0 && !pq.empty()) {
        auto e = pq.top(); pq.pop();
        if (!selected[e.to]) {          // 還沒被選進來的點才需要考慮
            selected[e.to] = true;      // 選取此點
            min_cost += e.weight;
            for (auto ne: g[e.to]) {   // 將此點對外的連線加進 pq
                if (!selected[ne.to]) {     // 只有連接目標還沒被選取的才加進 pq
                    pq.push(ne);
                }
            }
            remain_edges--;             // 選中的邊少一個
        }
    }
    return min_cost;
}

int main()
{
    stringstream    sin(input);
    Graph   G;
    int     n, a, b, r;

    sin >> n;
    G.resize(n);    // 有 n 個節點，從 0 號開始編號

    while (sin >> a >> b >> r) {
        G[a].push_back({b, r});
        G[b].push_back({a, r});
    }
    cout << mst_prim(G) << '\n';
    return 0;
}