#include<fstream>
#include<algorithm>
#define nmax 200002
#define mmax 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int M,N,idx[mmax],sef[nmax],nrc[nmax],x,y,x1,y1,t,i,k,s,j;
char viz[mmax];

struct muchie{
    int x,y,c;
}L[mmax];

int cmp(int a, int b){
    ///vom compara L[a] cu L[b]
    if(L[a].c<L[b].c){
        return 1;
    }
    else return 0;
}

int main ()
{
    fin>>N>>M;
    for(i=1;i<=M;i++){
        fin>>L[i].x>>L[i].y>>L[i].c;
        idx[i]=i;
    }
    sort(idx+1,idx+M+1,cmp);
    ///L[idx[1]].c<=L[idx[2]].c<=...<=L[idx[M]].c
    ///vom selecta N-1 muchii care au suma costurilor minima
    for(i=1;i<=N;i++){
        sef[i]=i;
        nrc[i]=1;
    }
    k=0;
    s=0;
    for(i=1;i<=M;i++){
        j=idx[i];
        x=L[j].x;
        while(x!=sef[x]){
            x=sef[x];
        }
        ///propagam lenes pe x ca sef al tuturor varfurilor de pe traseu
        x1=L[j].x;
        while(x1!=x){
            t=sef[x1];
            sef[x1]=x;
            x1=t;
        }
        y=L[j].y;
        while(y!=sef[y]){
            y=sef[y];
        }
        ///propagam lenes pe y ca sef al tuturor varfurilor de pe traseu
        y1=L[j].y;
        while(y1!=y){
            t=sef[y1];
            sef[y1]=y;
            y1=t;
        }
        if(x!=y){
            k++;
            viz[j]=1;
            s+=L[j].c;
            if(k==N-1){
                break;
            }
            ///unificam cele 2 componente
            ///vom conecta componenta cu mai putine elemente la cealalta
            ///vom afla pentru fiecare componenta reprezentantul, seful suprem
            ///sef suprem va fi un varf x cu proprietatea sef[x]=x

            if(nrc[x]<nrc[y]){
                nrc[y]+=nrc[x];
                sef[x]=y;
            }
            else{
                nrc[x]+=nrc[y];
                sef[y]=x;
            }
        }
    }
    fout<<s<<'\n';
    fout<<N-1<<'\n';
    for(i=1;i<=M;i++){
        if(viz[i]==1){
            fout<<L[i].x<<" "<<L[i].y<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}