#include <fstream>
#include <algorithm>
#define NMAX 400010

using namespace std;


FILE *fin,*fout;


int n,C[NMAX],m,Cost;
int minim,maxim;
int cati_de1=1;

struct elem{int x; int y; int cost;} muchie[NMAX],retin[NMAX];

int comp(elem a, elem b)
{
    if(a.cost<b.cost) return 1;
    if(a.cost==b.cost && a.x<b.x) return 1;
    if(a.cost==b.cost && a.x==b.x && a.y<b.y) return 1;
    return 0;
}

int main()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int i,j,z=0,k;
    fscanf(fin,"%d%d",&n,&m);
    //fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d",&muchie[i].x);
        fscanf(fin,"%d",&muchie[i].y);
        fscanf(fin,"%d",&muchie[i].cost);
        //fin >> muchie[i].x;
        //fin >> muchie[i].y;
        //fin >> muchie[i].cost;
        C[i]=i;
    }
    sort(muchie+1,muchie+m+1,comp);

    i=1;
    for(k=1;k<n;k++)
    {
        if(C[muchie[i].x]<C[muchie[i].y])
            minim=C[muchie[i].x],maxim=C[muchie[i].y];
        else minim=C[muchie[i].y],maxim=C[muchie[i].x];
        if(minim!=maxim)
        {
            for(j=1;j<=n;j++)   if(C[j]==maxim) C[j]=minim;
            z++;
            retin[z]=muchie[i];
            Cost+=muchie[i].cost;
        }
        do
        {
            i++;
        }
        while(C[muchie[i].x]==C[muchie[i].y]);
    }
    fprintf(fout,"%d\n%d\n",Cost,n-1);
    //fout << Cost << '\n';
    //fout << n-1 << '\n';
    for(i=1;i<n;i++)
        fprintf(fout,"%d %d\n",retin[i].x,retin[i].y);
        //fout << retin[i].x << ' ' << retin[i].y  << '\n';
    return 0;
}