//Link Info Arena: https://www.infoarena.ro/problema/apm
//Minimum spanning tree using Kruskal's algorithm
//Complexity:
//1. disjoint set union find: O(mlogn)
//2. vector: O(mlogn+n^2)
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
ofstream g("apm.out");


struct Muchie{
    int sursa;
    int destinatie;
    int pondere;
};
int N,M; //retinem global nr de noduri si muchii;
vector<Muchie> lista_muchii; //retinem muchiile intr-o lista de muchii pentru a le putea sorta mai usor
vector<Muchie> MST; //retinem muchiile din arborele nostru de cost minim
int r[1000]; //culoarea(reprezentantul componentei care contine varful u)
int cost=0;

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
    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;
        temporar.destinatie=Y;
        temporar.pondere=C;
        lista_muchii.push_back(temporar);
    }
    f.close();
}

bool comparare(Muchie a, Muchie b){
    return a.pondere<b.pondere;
}
void afisare_lista_muchii(vector<Muchie> &lista){
    for(auto uv: lista){
        cout<<uv.sursa<<" "<<uv.destinatie<<" "<<uv.pondere<<endl;
    }
}
void initializare(int v){
    r[v]=v;
}
int reprez(int u){
    return r[u];

}

void reuneste(int u, int v){
    int r1=reprez(u); // r1=r[u]
    int r2=reprez(v); // r2=r[v]
    for(int k=1;k<=N;k++){
        if(r[k]==r2){
            r[k]=r1;
        }
    }
}


void Kruskal_nu_chiar_optim(){
    sort(lista_muchii.begin(),lista_muchii.end(),comparare);
    for(int v=1;v<=N;v++){
        initializare(v);
    }
    int nr_muchii_selectate=0;
    for(auto uv:lista_muchii){
        if(reprez(uv.sursa)!=reprez(uv.destinatie)){
            MST.push_back(uv);
            reuneste(uv.sursa,uv.destinatie);
            nr_muchii_selectate+=1;
            cost=cost+uv.pondere;
            if(nr_muchii_selectate==N-1)
                break;
        }
    }
}


int main(){
    citire_graf("apm.in");
    Kruskal_nu_chiar_optim(); 
    //cout<<"Afisare lista muchii din MST"<<endl;
    g<<cost<<endl;
    g<<MST.size()<<endl;
    for(auto uv: MST){
        g<<uv.sursa<<" "<<uv.destinatie<<" "<<endl;
    }
    /* afisare_lista_muchii(MST);
    cout<<endl<<endl; */
    g.close();
    return 0;
}