PRIIIIIM

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

struct arista {
    int desde, hasta, costo;
    arista (int a, int b, int k) : desde(a), hasta(b), costo(k) {}
};

bool operator< (const arista &a, const arista &b)
{
    return a.costo > b.costo;
}

struct grafo {
    vector< vector<arista> > ady;
    vector<bool> visit;
    int n, m;

    void leer()
    {
        cin>>n>>m;

        ady.resize(n+1);
        visit = vector<bool> (n+1, false);

        int a, b, k;
        for (int i=0; i<m; i++)
        {
            cin>>a>>b>>k;
            ady[a].push_back( arista(a,b,k) );
            ady[b].push_back( arista(b,a,k) );
        }
    }

    vector<arista> Prim ()
    {
        vector<arista>  arbol;
        priority_queue<arista> pq;

        visit[1] = true;
        for(int i=0; i<ady[1].size(); i++)
            pq.push( ady[1][i] );

        while(pq.size() && arbol.size()<n-1 )
        {
            arista a = pq.top();
            pq.pop();

            int nodo = a.hasta;
            if (visit[nodo])
                continue;

            visit[nodo] = true;
            arbol.push_back( a );

            for(int i=0; i<ady[nodo].size(); i++)
                if (!visit[ady[nodo][i].hasta])
                    pq.push( ady[nodo][i] );
        }

        return arbol;
    }
};

int main()
{
    vector<arista> arbol;
    grafo g;

    g.leer();
    arbol = g.Prim();

    int peso = 0;
    for(int i=0; i<arbol.size(); i++)
    {
        cout<<arbol[i].desde<<" "<<arbol[i].hasta<<" "<<arbol[i].costo<<endl;
        peso+=arbol[i].costo;
    }


    cout<<peso;

    return 0;
}