#include <fstream>
#include <algorithm>
#define nmax 200000
#define mmax 400000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
int apm[nmax], c[nmax]; //apm - indicii celor n-1 muchii selectate
struct muchie{
    int x, y;
    int cost;
};
muchie gr[mmax];
int costApm;

void citire();
bool sortare(muchie, muchie);
void kruskal();
void afisare();

int main(){
    citire();
    sort(gr+1, gr+m+1, sortare);
    //for(int i=1; i<=m; ++i) fout<<gr[i].x<<' '<<gr[i].y<<' '<<gr[i].cost<<'\n';
    kruskal();
    afisare();
    return 0;
}

void citire(){
    fin>>n>>m;
    int i;
    for(i=1; i<=m; ++i)
        fin>>gr[i].x>>gr[i].y>>gr[i].cost;
    for(i=1; i<=n; ++i) c[i]=i;
}

bool sortare(muchie x, muchie y){
    return x.cost < y.cost;
}

void kruskal(){
    int nrM=0, j, minim, maxim;
    for(int i=1; nrM!=n-1; ++i){ //sunt la muchia i
        if(c[gr[i].x]!=c[gr[i].y]){
            apm[++nrM]=i; //retun muchia
            costApm+=gr[i].cost;
            //unific Cc ale extremitatilor
            if(c[gr[i].x]>c[gr[i].y]){
                minim=c[gr[i].y];
                maxim=c[gr[i].x];
            }
            else{
                minim=c[gr[i].x];
                maxim=c[gr[i].y];
            }
            for(j=1; j<=n; ++j) if(c[j]==maxim) c[j]=minim;
        }
    }
}

void afisare(){
    fout<<costApm<<'\n'<<n-1<<'\n';
    for(int i=1; i<=n-1; ++i) fout<<gr[apm[i]].x<<' '<<gr[apm[i]].y<<'\n';
}