#include <stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

int *p,*x,*y,*c,cost,*nrm;
int n,m;
vector<int> vm;

int grupa(int i)
{
    if (p[i]==i) return i;
    p[i]=grupa(p[i]);
    return p[i];
}

void reuniune(int i,int j)
{
    p[grupa(i)]=grupa(j);
}

bool cmpf(int i,int j)
{
    return(c[i]<c[j]);
}

int main()
{
    FILE *f,*g;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    p=new int[200000];
    x=new int[400000];
    y=new int[400000];
    c=new int[400000];
    nrm=new int[400000];
    fscanf(f,"%d %d\n",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d\n",&x[i],&y[i],&c[i]);
        nrm[i]=i;
    }
    fclose(f);
    for(int i=1;i<=n;i++) p[i]=i;
    sort(nrm+1,nrm+m+1,cmpf);
    for(int i=1;i<=m;i++) if(grupa(x[nrm[i]])!=grupa(y[nrm[i]])) {cost+=c[nrm[i]];
                                                                  reuniune(x[nrm[i]],y[nrm[i]]);
                                                                  vm.push_back(nrm[i]);}
    fprintf(g,"%d\n",cost);
    fprintf(g,"%d\n",n-1);
    for(int i=0;i<n-1;++i) fprintf(g,"%d %d\n",x[vm[i]],y[vm[i]]);
    fclose(g);
    return 0;
}