#include <iostream>
#include <fstream>
#include <utility>
#include <stdlib.h>

using namespace std;


int main()
{
   FILE *f,*g;

   int n,m,x,y,c,total=0,k=1,min;
   pair <int,int> *p,*q;
   int *cost;
   bool *viz;

   f=fopen("apm.in","r");
   fscanf(f,"%d%d",&n,&m);


   p=new pair<int,int>[m];
   q=new pair<int,int>[n-1];
   cost=new int[m];
   viz=new bool[n];

   for(int i=0;i<n;i++) viz[i]=0;


   for(int i=0;i<m;i++)
   {
       fscanf(f,"%d%d%d",&x,&y,&c);
       p[i]=make_pair(x,y);
       cost[i]=c;
   }
   fclose(f);

   viz[0]=1;int poz=0; x=0;

   while(k<n)
   {
       min=1000;
       for(int i=0;i<m;i++)
       if(cost[i]<min && ( (viz[p[i].first-1] && !viz[p[i].second-1]) ||(!viz[p[i].first-1] && viz[p[i].second-1]) ) )
       {
           min=cost[i];
           poz=i;
       }

       k++; total+=min;
       if(!viz[p[poz].second-1]) viz[p[poz].second-1]=1;
       else if(!viz[p[poz].first-1]) viz[p[poz].first-1]=1;

       q[x++]=make_pair(p[poz].first,p[poz].second);
   }

  g=fopen("apm.out","w");
  fprintf(g,"%d\n%d\n",total,n-1);
  for(int i=0;i<n-1;i++) fprintf(g,"%d %d\n",q[i].first,q[i].second);
  gclose(g);

   return 0;
}