/*
    Initial fiecare nod se afla intr-o componenta conexa proprie. La
    fiecare pas, se alege muchia de cost minim ce are extremitatile in
    2 componente conexe distincte. Cele 2 componente se reunesc.
*/
#include <bits/stdc++.h>

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

typedef pair <int, pair < int , int > > ppair; ///x, y si cost
ppair arbore[400005];
pair <int,int>n[400005];
vector <pair < int , int > >apm;  ///perechile x&y --> muchiile ce formeaza APM
int componente,costTotal,nods,m;

struct comp1{
    bool operator()(ppair x, ppair y){
        return (x.second.second < y.second.second);  ///cost X < cost Y
    }
};

int Find(int x){  ///CAUTA CHEIA DIN GRUPUL LUI X
    if(n[x].first!=x) n[x].first=Find(n[x].first);
    return n[x].first;
}

void Unite(int x, int y){
    int xRoot=Find(x);
    int yRoot=Find(y);
    if(n[xRoot].second > n[yRoot].second){
        n[xRoot].second += n[yRoot].second;
        n[yRoot].first = n[xRoot].first;
    }
    else{
        n[yRoot].second += n[xRoot].second;
        n[xRoot].first = n[yRoot].first;
    }
    componente--;
}

int citire(){
    f>>nods>>m;
    for(int i=1;i<=m;++i){
        f>>arbore[i].first>>arbore[i].second.first>>arbore[i].second.second;
    }

}

void make_set(){
    for(int i=1;i<=nods;++i){
        n[i].first=i;  ///CHEIA GRUPULUI
        n[i].second=1; ///MARIMEA GRUPULUI
    }
}

int main()
{
    citire();
    make_set();
    componente=nods;
    sort(arbore+1,arbore+m+1,comp1());
    for(int i=1;i<=m;++i){
        if (componente==1) break;
        int x=arbore[i].first;
        int y=arbore[i].second.first;
        int cost=arbore[i].second.second;
        if(Find(x)!=Find(y)){
            Unite(x,y);
            costTotal+=cost;
            apm.push_back(make_pair(x,y));
        }
    }
    g<<costTotal<<'\n'<<nods-1<<'\n';
    //vector < pair < int, int > > ::iterator it;
    for(auto x: apm){
        g<<x.second<<' '<<x.first<<'\n';
    }

    f.close(); g.close();
    return 0;
}