#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mmax 400005
#define nmax 200005
using namespace std;
typedef pair < int , pair < int , int > > ppair;
pair <int,int> n[nmax];
int m,nods,componente,i;
vector < pair <int , int > > apm;
ppair arbore[mmax];
ifstream in("apm.in");
ofstream out("apm.out");
vector < pair < int , int > > ::iterator it;
struct comp{
    bool operator()(ppair x, ppair y){
                return (x.second.second < y.second.second);
    }
};

int Find(int x){
    if(n[x].first != x) n[x].first=Find(n[x].first);
    return n[x].first;
}

void Union(int x, int y){
    int xRoot=Find(x);
    int yRoot=Find(y);

    if(xRoot > yRoot){
        n[xRoot].second += n[yRoot].second;
        n[xRoot].first=n[yRoot].first;
    }
    else {
        n[yRoot].second += n[xRoot].second;
        n[yRoot].first=n[xRoot].first;
    }
    componente--;
}

void read(){
    in>>nods>>m;
    for(i=1;i<=m;++i){
        in>>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;
        n[i].second=1;
    }

}

int main()
{   read();
    make_set();
    sort(arbore+1, arbore+m+1 ,comp());
    int costTotal=0;
    componente=nods;
    for(i=1;i<=m;++i){
        if(componente==1) break;
        int x=arbore[i].first;
        int y=arbore[i].second.first;
        int c=arbore[i].second.second;
        if(Find(x)!=Find(y)){
                Union(x,y);
                costTotal += c;
                apm.push_back(make_pair(x,y));
        }
    }
    out<<costTotal<<'\n'<<nods-1<<'\n';
    for(it=apm.begin();it!=apm.end();++it){
        out<<it->second<<' '<<it->first<<'\n';
    }
    return 0;
}