//#include <fstream>
#include <stdio.h>
#define dmax 200005

/*using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");*/

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

struct muchie
{
    int x,y,cost;
};
muchie u[dmax],arb[dmax];
int n,m,costAPM,sel[dmax],nrm;

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

void quick(int st, int dr)
{
      int i=st, j=dr, pivot=u[(st+dr+1)/2].cost;
    muchie aux;
      /* partition */
      while (i<=j)
      {
            while (u[i].cost<pivot)  i++;
            while (u[j].cost>pivot)  j--;
            if (i<=j)
            {
                  aux=u[i];
                  u[i]=u[j];
                  u[j]=aux;
                  i++;
                  j--;
            }
      }

      /* recursion */
      if (st<j)
        quick(st,j);
      if (i<dr)
        quick(i,dr);
}


/*void sortare()
{
    muchie aux;
    int i,j;
    for(i=1;i<=m-1;i++)
        for(j=i+1;j<=m;j++)
            if(u[i].cost>u[j].cost)
               {
                   aux=u[i];
                   u[i]=u[j];
                   u[j]=aux;
               }
}*/

void PRIM()
{
    int i,x,y,cost;
    x=u[1].x;y=u[1].y;cost=u[1].cost;arb[1].cost=cost;
    sel[x]=sel[y]=1;costAPM=costAPM+cost;
    arb[1].x=x;arb[1].y=y;
    //fout<<"Am selectat: "<<x<<" "<<y<<" "<<cost<<'\n';
    //fout<<sel[x]<<" "<<sel[y]<<'\n';
    nrm=1;
    while(nrm<n-1)
        for(i=2;i<=m;i++)
            {
                x=u[i].x;y=u[i].y;cost=u[i].cost;
                if(sel[x]!=sel[y])
                   {
                   //    fout<<"Am selectat: "<<x<<" "<<y<<" "<<cost<<'\n';
                       nrm=nrm+1;
                       sel[x]=sel[y]=1;costAPM+=cost;
                       arb[nrm].x=x;arb[nrm].y=y;arb[nrm].cost=cost;
                       //fout<<sel[x]<<" "<<sel[y]<<'\n';
                       break;
                   }
            }
}

int main()
{
    int i;
    citire();
    quick(1,m);
    //sortare();
    /*fout<<"Muchii sortate dupa cost\n";
    for(i=1;i<=m;i++)
        fout<<u[i].x<<" "<<u[i].y<<" "<<u[i].cost<<'\n';
    fout<<"Ordinea de selectare a muchiilor prin algoritmul lui PRIM\n";*/
    PRIM();
    //fout<<costAPM<<'\n';
    //fout<<"Muchiile arborelui\n";
    //fout<<nrm<<'\n';
    fprintf(fout,"%d\n%d\n",costAPM,nrm);
    for(i=1;i<=nrm;i++)
        //fout<<arb[i].x<<" "<<arb[i].y<<'\n';
        fprintf(fout,"%d %d\n",arb[i].x,arb[i].y);
    return 0;
}