#include <iostream>
#include <fstream>
#include <utility>
#include <cstdlib>

using namespace std;

struct muchie
{
    int cost;
    pair<int,int> p;
}*K;

int comp(const void *a,const void *b)
{
    muchie *A,*B;
    A=(muchie *)a;
    B=(muchie *)b;
    return A->cost-B->cost;
}

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

  int m,n,total=0,*con,x,y,c;
  pair<int,int> *Q;

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

  K=new muchie[m];
  con=new int[n];
  Q=new pair<int,int>[n-1];

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

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

  qsort(K,m,sizeof(muchie),comp);

  int k=0,q=0,a,b,min,u,v;
  x=0;
  while(k<n-1)
  {
      u=a=K[q].p.first;
      v=b=K[q].p.second;
      min=K[q].cost;

      while(con[u]) u=con[u];
      while(con[v]) v=con[v];

      if(u!=v)
      {
          k++;
          total+=min;
          Q[x++]=make_pair(a,b);
          con[v]=u;
      }
     q++;
  }

  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);
  fclose(g);

   return 0;
}