#include <stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
FILE *f=fopen("apm.in","r"),*g=fopen("apm.out","w");
int X[400001],Y[400001],C[400001],GR[200001],IND[400001],s=0,n,m,h[200001];

vector <int>v;

void citire(){
int i;
    fscanf(f,"%d %d",&n,&m);
    for(i=1; i<=m; i++){
        fscanf(f,"%d %d %d",&X[i],&Y[i],&C[i]);
        IND[i]=i; //punem in ind indicele muchiei in ordinea citirii
    }
    /*for(i=1; i<=n; i++){
        GR[i]=i; //punem in gr grupa din care face parte
                 //adica reprezentatul cu indicele cel mai mare din acea grupa
    }*/
}

bool cmp(int i,int j){
    return (C[i]<C[j]);
}

int grupa(int i){
    /*if(GR[i]==i){return i;}
    else{
        GR[i]=grupa(GR[i]);
        return GR[i];
    }*/

    int cauta,ok,prec;
    cauta=i;
    while(GR[cauta]!=0){cauta=GR[cauta];}

    ok=cauta;
    cauta=i;

    while(GR[cauta]!=0){
        prec=cauta;
        cauta=GR[cauta];
        GR[prec]=ok;
    }
    return ok;

}
void reuneste(int i,int j){
    int x=grupa(i),y=grupa(j);
    if(h[x]>h[y]){GR[y]=x;}
    else if(h[x]<h[y]){GR[x]=y;}
    else{GR[x]=y; h[y]++;}
    //GR[grupa(i)]=grupa(j);
}

void APM(){
int i,st,dr;
    for(i=1; i<=m; i++){
        st=X[IND[i]];
        dr=Y[IND[i]];
        if(grupa(st)!=grupa(dr)){
            //adica daca nu au acelasi reprez(adica nu form ciclu)
            s+=C[IND[i]];
            reuneste(st,dr); //fac parte din aceeasi grupa
            v.push_back(IND[i]);

        }
    }
}

void afisare(){
int i;
    fprintf(g,"%d\n",s);
    fprintf(g,"%d\n",n-1);
    for(i=0; i<n-1; i++){
        fprintf(g,"%d %d\n",X[v[i]],Y[v[i]]);
    }
}
int main()
{
    citire();
    sort(IND+1,IND+m+1,cmp); //sortam muchiile in ord cresc dupa costul lor
    APM();
    afisare();
    return 0;
}