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

typedef pair<int,pair<unsigned,unsigned> > EDGE;

unsigned Find(unsigned x,vector<unsigned> &parents){
    unsigned a=x;
    while(parents[a]!=a) a=parents[a];
    while(parents[x]!=a){
        unsigned b=parents[x];
        parents[x]=a;
        x=b;
    }
    return a;
}
void Union(unsigned xr, unsigned yr,
           vector<unsigned> &parents, vector<unsigned> &ranks){
    if(ranks[xr]>ranks[yr]) parents[yr]=xr;
    else if(ranks[xr]<ranks[yr]) parents[xr]=yr;
    else{
        parents[xr]=yr;
        ranks[yr]++;
    }
}


int main(){
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    unsigned N,M;
    fin>>N>>M;
    vector<EDGE> edges(M);
    for(unsigned i=0;i<M;++i){
        fin>>edges[i].second.first; edges[i].second.first--;
        fin>>edges[i].second.second; edges[i].second.second--;
        fin>>edges[i].first;
    }
    sort(edges.begin(),edges.end());

    int Smin=0; unsigned nred=0;
    vector<bool> isintree(M,false);

    vector<unsigned> parents(N),ranks(N,0);
    for(unsigned i=0;i<N;++i) parents[i]=i;

    for(unsigned i=0;i<M;++i){
        unsigned a=Find(edges[i].second.first,parents);
        unsigned b=Find(edges[i].second.second,parents);
        if(a!=b){
            Union(a,b,parents,ranks);
            nred++; Smin+=edges[i].first;
            isintree[i]=true;
        }
    }
    fout<<Smin<<'\n'<<nred<<'\n';
    for(unsigned i=0;i<M;++i)
        if(isintree[i]) fout<<edges[i].second.first+1<<' '<<edges[i].second.second+1<<'\n';
}