// Pentru a construi un arbore partial de cost minim (APM),
// vrem sa adaugam muchii de cost minim, astfel incat acestea 
// sa formeze o submultime a multimii muchiilor APM.

// Kruskal:
// Alegem muchii de cost minim astfel incat extremitatile lor 
// sa apartina la componente conexe diferite.

// Initial, la Kruskal, avem n noduri izolate (n componente conexe).
// Incepem sa unim muchii de cost minim pentru a forma arborele.

// La fiecare pas, muchiile selectate formeaza o padure de arbori.
// Selectam o muchie de cost minim care uneste doi arbori 
// din padurea curenta.

// Ordonam muchiile in ordine crescatoare dupa cost.
// Folosim o lista de muchii pentru a memora costurile si extremitatile.
// Verificam printr-o parcurgere daca extremitatile muchiei sunt 
// deja unite (conectate printr-un lant de muchii) - complexitate O(m * n).

// Operatii necesare pentru algoritmul Kruskal:
// Initializare(u) - creeaza o componenta cu un singur varf u.
// Reprez(u) - returneaza reprezentantul (radacina) componentei 
//             care contine varful u.
// Reuneste(u, v) - uneste componentele care contin u si v.

// Modalitati de implementare pentru Kruskal:
// 1) Cand vrem sa adaugam o noua muchie, parcurgem componenta 
// conexa a extremitatii care nu este in arborele construit 
// si actualizam componentele pentru fiecare nod in acea componenta.
// 2) Retinem un vector de tati pentru fiecare nod si actualizam doar 
// radacina din arbore pentru extremitatea muchiei, nu intreaga componenta conexa.

// Radacina unui arbore va deveni fiul altui arbore cand se unesc.
// Trebuie sa tinem cont de inaltimea si dimensiunea arborilor pentru eficienta.

// Complexitati Kruskal:
// 1) O(M log M + N^2) - cu parcurgere a componentelor
// 2) O(M log M + M log* N) - folosind disjoint-set

//----------------------------------------------------------

// Prim:
// Alegem o muchie de cost minim care are o extremitate in arborele
// construit si cealalta extremitate in afara arborelui.

// La Prim, pornim de la un nod sursa si adaugam pe rand noduri 
// pentru care exista o muchie de cost minim catre arborele construit.

// La fiecare pas, muchiile selectate formeaza un arbore.

// Selectam o muchie de cost minim care uneste un nod din arbore 
// cu un nod in afara arborelui.


//Complexitatea este:O(MlogM+Mlog*N)
/*
#include <fstream>
#include <algorithm>
#include<vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie{
    int nod1,nod2,cost;
};
bool cmp(muchie a,muchie b){
    return a.cost<b.cost;
}
vector<muchie>muchii;
vector<int>cardinal,tata;
vector<pair<int,int>>rasp;
int gasesteRadacina(int nod){
    while(tata[nod]!=nod){
        nod=tata[nod];
    }
    return nod;
}
void uneste(int nodA,int nodB){
    nodA=gasesteRadacina(nodA);
    nodB=gasesteRadacina(nodB);

    if(cardinal[nodA]>cardinal[nodB]){
        cardinal[nodA]+=cardinal[nodB];
        tata[nodB]=tata[nodA];
        cardinal[nodB]=0;

    }else{
        cardinal[nodB]+=cardinal[nodA];
        tata[nodA]=tata[nodB];
        cardinal[nodA]=0;

    }
}
int n,m;
int main(){
    cin>>n>>m;
    muchii.resize(m+1);
    cardinal.resize(n+1,1);
    tata.resize(n+1);
    for(int i=1;i<=m;i++){
        cin>>muchii[i].nod1>>muchii[i].nod2>>muchii[i].cost;
    }
    for(int i=1;i<=n;i++){
        tata[i]=i;
    }
    sort(muchii.begin()+1,muchii.end(),cmp);
    int nodA,nodB,cost=0;
    for(int i=1;i<=m;i++){
        nodA=gasesteRadacina(muchii[i].nod1);
        nodB=gasesteRadacina(muchii[i].nod2);
        if(nodA==nodB){
            continue;
        }
        uneste(muchii[i].nod1,muchii[i].nod2);
        rasp.push_back({muchii[i].nod1,muchii[i].nod2});
        cost+=muchii[i].cost;
    }
    cout<<cost<<'\n';
    cout<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
    muchii.clear();
    cardinal.clear();
    tata.clear();
}
*/

//Complexitatea este:O(MlogM+Mlog*N)
#include <fstream>
#include <algorithm>
#include<vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie{
    int nod1,nod2,cost;
};
bool cmp(muchie a,muchie b){
    return a.cost<b.cost;
}

vector<muchie>muchii;
vector<vector<int>>componenta_conexa;
vector<pair<int,int>>rasp;
vector<int>nr_comp;
int n,m;
int main(){
    cin>>n>>m;
    muchii.resize(m+1);
    componenta_conexa.resize(n+1);
    nr_comp.resize(n+1);
    
    for(int i=1;i<=m;i++){
        cin>>muchii[i].nod1>>muchii[i].nod2>>muchii[i].cost;
    }
    for(int i=1;i<=n;i++){
        componenta_conexa[i].push_back(i);
        nr_comp[i]=i;
    }
    sort(muchii.begin()+1,muchii.end(),cmp);

    int cost=0,aux;
    for(int i=1;i<=m;i++){

        if(nr_comp[muchii[i].nod1]==nr_comp[muchii[i].nod2]){
            continue;
        }
        vector<int>comp_temp=componenta_conexa[nr_comp[muchii[i].nod2]];
        int nr=nr_comp[muchii[i].nod2];

        for(int j=0;j<comp_temp.size();j++){
          nr_comp[comp_temp[j]]=nr_comp[muchii[i].nod1];
          componenta_conexa[nr_comp[muchii[i].nod1]].push_back(comp_temp[j]);

        }
        
        comp_temp.clear();
        componenta_conexa[nr].clear();
        rasp.push_back({muchii[i].nod1,muchii[i].nod2});
        cost+=muchii[i].cost;
    }

  
    cout<<cost<<'\n';
    cout<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
    muchii.clear();
    componenta_conexa.clear();
    nr_comp.clear();
    rasp.clear();
}