#include <stdio.h>
#include <algorithm>
#define mmax 400100 
#define nmax 200100
using namespace std;
 
struct muchie {int x,y,c;} muc[mmax];
int N,M,TT[nmax],S,SOL[nmax][2];

void citire()
     {freopen("apm.in","r",stdin);
      int i;
      scanf("%d %d",&N,&M);
      for(i=1;i<=M;i++)    scanf("%d %d %d",&muc[i].x,&muc[i].y,&muc[i].c);
      for(i=1;i<=N;i++)    TT[i]=i;
      fclose(stdin);
      }
bool cmp(muchie a,muchie b)     {return a.c<b.c;}
int root(int nod)
      {int R,x;
       for(R=nod;R!=TT[R];R=TT[R]);
       for(;nod!=TT[nod];)
                  {x=TT[nod];
                   TT[nod]=R;
                   nod=x;
                   }
       return R;
       }
void rezolva()
     {int i,nrmuc=0,R1,R2;
      for(i=1;i<=M && nrmuc<N-1;i++)
                {R1=root(muc[i].x);R2=root(muc[i].y);
                 if(R1!=R2)    {S+=muc[i].c;TT[R2]=R1;
                                SOL[++nrmuc][0]=muc[i].x;SOL[nrmuc][1]=muc[i].y;
                                }
                 }
     }
void scriere()
     {freopen("apm.out","w",stdout);
      int i;
      printf("%d\n%d\n",S,N-1);
      for(i=1;i<N;i++)  printf("%d %d\n",SOL[i][0],SOL[i][1]);
      fclose(stdout);
      }
int main()
    {citire();
     sort(muc+1,muc+1+M,cmp);
     rezolva();
     scriere();
     return 0;
     }