#include <cstdio>
#include <algorithm>
#define MMAX 400005
#define NMAX 200005

using namespace std;

FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");

struct muchie{
int x,y;
double cost;
};

void citire();
void kruskal();
bool compara(muchie a,muchie b);
void afisare();

muchie graf[MMAX];
int apm[NMAX],conex[NMAX]; //aici retinem indicii muchiilor selectate
int n,m;
int costapm;

int main()
{
citire();
sort(graf,graf+m, compara );
kruskal();
afisare();
    return 0;
}

bool compara(muchie a,muchie b)
{
return a.cost<b.cost;
}

void kruskal()
{
int i,j,k,minim,maxim,poz=0;
for (i=1;i<=n-1;i++)
     for (j=poz;j<m;j++)
          if ( conex[graf[j].x]!=conex[graf[j].y])
             {
              costapm+=graf[j].cost;
              apm[i]=j; //poz++;
              if (conex[graf[j].x]<conex[graf[j].y])
                 {
                  minim=conex[graf[j].x];
                  maxim=conex[graf[j].y];
                 }
                 else
                 {
                  minim=conex[graf[j].y];
                  maxim=conex[graf[j].x];
                 }
              for (k=1;k<=n;k++)
                   if (conex[k]==maxim) conex[k]=minim;
              poz=j+1;
              break;
             }
             //else poz++;
}

void afisare()
{
int i;
fprintf(fout,"%d\n",costapm);
fprintf(fout,"%d\n",n-1);
for (i=1;i<=n-1;i++)
     fprintf(fout,"%d %d\n",graf[ apm[i] ].x,graf[ apm[i] ].y);
//for (i=0;i<m;i++)
//     fprintf(fout,"%d %d %lf\n",graf[i].x,graf[i].y,graf[i].cost);
     //fout<<graf[i].x<<' '<<graf[i].y<<' '<<graf[i].cost<<'\n';
}

void citire()
{
int i;
fscanf(fin,"%d %d",&n,&m);
for (i=0;i<m;i++)
     fscanf(fin,"%d %d %lf",&graf[i].x,&graf[i].y,&graf[i].cost);
for (i=1;i<=n;i++) conex[i]=i;
}