#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

struct edge{
    int a,b; //vertex
    int c; //cost
};

struct sedge{
    int a,b;
};


bool cmp(const edge& lhs, const edge& rhs){
    return (lhs.c<rhs.c);
}

vector<sedge> ds;//disjoint set container

void makeset(int nod){
    ds[nod].a=nod;// parent
    ds[nod].b=0; //rank
}

int findc(int nod){
    if(ds[nod].a!=nod)
        ds[nod].a=findc(ds[nod].a);
    return ds[nod].a;
}

void uni(int x,int y){
    int xr=findc(x);
    int yr=findc(y);

    if(xr!=yr){
        if (ds[xr].b<ds[yr].b)
            ds[xr].a=yr;
        else if (ds[xr].b>ds[yr].b)
            ds[yr].a=xr;
        else{
            ds[yr].a=xr;
            ds[xr].b+=1;
        }
    }
}



int main(){
    ifstream ifs("apm.in");
    ofstream ofs("apm.out");

    int N,M; //N-noduri, M-muchii
    ifs>>N>>M;

    vector<edge> g(M);
    vector<sedge> ans(N);
    ds.resize(N);

    for(int i=0; i<N; i++)
        makeset(i);

    for(int i=0; i<M; i++){
        ifs>>g[i].a>>g[i].b>>g[i].c;
        g[i].a--;
        g[i].b--;
    }

    sort(g.begin(),g.end(),cmp); //sort edges

    int nr=0;
    int cost=0;
    for(int i=0; (i<M)&&(nr<N); i++){
        int xr=findc(g[i].a);
        int yr=findc(g[i].b);

        if(xr!=yr){
            ans[nr].a=g[i].a;
            ans[nr].b=g[i].b;
            nr++;
            cost+=g[i].c;
            uni(g[i].a,g[i].b);// union
        }
    }


    ofs<<cost<<"\n";
    ofs<<nr<<"\n";
    for(unsigned i=0; i<ans.size()-1; i++)
        ofs<<ans[i].a+1<<" "<<ans[i].b+1<<"\n";
}