//Link Info Arena: https://www.infoarena.ro/problema/apm
//Minimum spanning tree using Kruskal's algorithm
//Complexity:
//1. folosim un vector de vizitat: O(n^2)
//2. min-heap pentru Q(multimea nodurilor neselectate in arbore): O(mlogn)

#include<iostream>
#include<fstream>
#include<vector>
#include<climits>
using namespace std;
ofstream g("apm.out");

struct Nod{
    int d; //fiecarui nod ii este asociat o eticheta d care reprezinta costul minim
    int tata; //fiecarui nod ii este asociat un parinte pentru care muchia (Nod, tata[Nod]) are cost minim d[Nod]
    bool vizitat; //verific daca nodul curent a fost sau nu adaugat in MST
};

struct Muchie{
    int sursa;
    int destinatie;
    int pondere;
};

int N,M,cost_total;
vector<Muchie> lista_muchii; //retinem muchiile intr-o lista de muchii pentru a le putea sorta mai usor
vector<Nod> Q; //multimea muchiilor neselectate in arbore
vector<Muchie> MST; //multimea muchiilor selectate in MST
vector<vector<int>> graf; //aici retinem o matrice de ponderi de la un nod la altul, pentru a verifica mai usor daca exista muchie de la un nod la altul 
//daca exista o pondere!=INT_MIN, atunci exista si o muchie

void initializare_graf(int N){
     graf.resize(N, vector<int>(N, INT_MIN));
}
void citire_graf(const char* fisier){
    ifstream f(fisier);
    if(!f.is_open()){
        cerr<<"Eroare la deschiderea fisierului";
        return;
    }
    f>>N>>M; //citim nr de noduri si muchii
    initializare_graf(N);

    Muchie temporar;
    for(int i=1; i<=M;i++){
        //pentru fiecare muchie citim nodul sursa, nodul destinatie si ponderea
        int X,Y,C;
        f>>X>>Y>>C;
        temporar.sursa=X-1;
        temporar.destinatie=Y-1;
        temporar.pondere=C;
        graf[X-1][Y-1]=C;
        graf[Y-1][X-1]=C;
        lista_muchii.push_back(temporar);
    }
    f.close();
}
void initializare_Q(){
    Q.resize(N);
    for(auto &nod: Q){
        nod.tata=0; //nodurile sunt nevizitate initial
        nod.d=INT_MAX; //costul minim initial este infinit
        nod.vizitat=false; //nodurile sunt nevizitate initial
    }
}
int cost_minim(){
    //initializam valoarea minima;
    int min=INT_MAX, min_index;
    for(int nod=0; nod<Q.size();nod++){
        if(Q[nod].vizitat==false && Q[nod].d<min){
            min=Q[nod].d;
            min_index=nod;
        }
    }
    return min_index;
}
void actualizare_d(int u){
    for(int v = 0 ; v<Q.size(); v++){
        if(Q[v].vizitat==false&&graf[u][v]!=INT_MIN&& graf[u][v]<Q[v].d){
            Q[v].tata=u;
            Q[v].d=graf[u][v];
        }
    }
}

void Prim_nu_chiar_optim(){
    //Pasul 1: Initializare
    initializare_Q();
    //Pasul 2: Alegem primul nod din multime
    Q[0].d=0; 
    Q[0].tata=-1; //primul nod este si radacina arborelui MST 
    Q[0].vizitat=true; //marchez primul nod ca fiind vizitat
    actualizare_d(0);
    for(int i=1; i<N;i++){
        //parcurgem toate nodurile
        //Pasul 3: extragem varful pt care avem d minim (i.e cost)
        int u = cost_minim();
        Q[u].vizitat=true; //marcam nodul ales ca fiind vizitat

        //Pasul 4: actualizam etichetele cu costurile vecinilor
        actualizare_d(u);
        //acum ar trebui sa adaug muchia de la tata[u] la u in MST
        Muchie temp;
        temp.sursa=Q[u].tata;
        temp.destinatie=u;
        temp.pondere=Q[u].d;
        MST.push_back(temp);
        //Actualizam si costul total
        cost_total+=Q[u].d;
    }

}
void afisare_lista_muchii(vector<Muchie> &lista){
    for(auto uv: lista){
        g<<uv.sursa+1<<" "<<uv.destinatie+1<<" "<<uv.pondere<<endl;
    }
}

int main(){
    citire_graf("apm.in");
    Prim_nu_chiar_optim();
    g<<cost_total<<endl;
    g<<MST.size()<<endl;
    afisare_lista_muchii(MST);
    g.close();
    return 0;
}