#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
typedef pair < int , pair < int , int > > ppair;
ppair arbore[400005];
pair < int , int > n[400005];
vector < pair < int , int > > apm;
int componente,costTotal,nods,m;
struct comp1{
    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 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(){
    in>>nods>>m;
    for(int 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()
{
    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 c=arbore[i].second.second;
        if(Find(x)!=Find(y)){
            Unite(x,y);
            costTotal+=c;
            apm.push_back(make_pair(x,y));
        }
    }
    out<<costTotal<<' '<<nods-1<<'\n';
    vector < pair < int, int > > ::iterator it;
    for(it=apm.begin();it!=apm.end();++it){
        out<<it->second<<' '<<it->first<<'\n';
    }
    return 0;
}