//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 Nod{
    int tata; //fiecare nod are/sau nu un parinte
    int h; //arborele cu radacina in Nod are inaltimea h 
};

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<Nod> multimi_disjuncte;
vector<Muchie> MST; //retinem muchiile din arborele nostru de cost minim
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-1;
        temporar.destinatie=Y-1;
        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(){
    multimi_disjuncte.resize(N);
    for(int i=0; i<N;i++){
        multimi_disjuncte[i].tata=-1; //initial nu exista niciun arbore construit
        multimi_disjuncte[i].h=0; //inaltimea arborelui din fiecare nod este 0
    }
}
int Find(int nod){
    if(multimi_disjuncte[nod].tata==-1)
        return nod;
    return multimi_disjuncte[nod].tata=Find(multimi_disjuncte[nod].tata); //COMPRIMARE DE CALE
}
void Union(int parinte_sursa, int parinte_destinatie){
    //Facem reuniunea celor doi arbori/multimi disjuncte in functie de inaltimea arborilor
    if(multimi_disjuncte[parinte_sursa].h>multimi_disjuncte[parinte_destinatie].h){
        multimi_disjuncte[parinte_destinatie].tata=parinte_sursa;
    }
    else if(multimi_disjuncte[parinte_sursa].h<multimi_disjuncte[parinte_destinatie].h){
        multimi_disjuncte[parinte_sursa].tata=parinte_destinatie;
    }
    else{
        //daca ambii arbori au aceeasi inaltime
        multimi_disjuncte[parinte_sursa].tata=parinte_destinatie;
        multimi_disjuncte[parinte_destinatie].h+=1; 
    }
}

void Kruskal(){
    initializare();
    //Pasul 1: Sortam lista de muchii in ordine crescatoare
    sort(lista_muchii.begin(),lista_muchii.end(), comparare);
    //Pasul 2: Adaugam la MST muchia de cost minim care nu formeaza un ciclu ce celelalte muchii adaugate
    int i=0,j=0;
    while(i < N-1 && j < M){
        int parinte_sursa=Find(lista_muchii[j].sursa); //gasim parintele absolut al submultimii
        int parinte_destinatie=Find(lista_muchii[j].destinatie);

        if(parinte_sursa==parinte_destinatie){
            ++j; continue; 
            //daca nodurile au acelasi parinte inseamna ca fac parte din aceeasi componenta conexa
            //prin urmare sarim muchia si mergem mai departe fara a o lua in calcul

        }
    
        // facem reuniunea celor 2 arbori
        Union(parinte_sursa,parinte_destinatie);
        MST.push_back(lista_muchii[j]); //adaugam muchia j in arborele nostru de cost minim
        cost+=lista_muchii[j].pondere; //adaugam ponderea la costul total
        ++i;
        ++j;
        
    }
    
}


int main(){
    citire_graf("apm.in");
    /* cout<<"Afisare lista initiala muchii: \n";
    afisare_lista_muchii(lista_muchii);
    cout<<endl<<endl; */
    Kruskal(); 
    //cout<<"Afisare lista muchii din MST"<<endl;
    g<<cost<<endl;
    g<<MST.size()<<endl;
    for(auto uv: MST){
        g<<uv.sursa+1<<" "<<uv.destinatie+1<<" "<<endl;
    }
    /* afisare_lista_muchii(MST);
    cout<<endl<<endl; */
  
    return 0;
}