#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()
{
  ifstream f("apm.in");
  int m,n,total=0,*con,x,y,c;
  pair<int,int> *Q;

  f>>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++)
   {
       f>>x>>y>>c;
       K[i].p=make_pair(x,y);
       K[i].cost=c;
   }

  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++;
  }

  ofstream g("apm.out");
  g<<total<<endl<<n-1<<endl;
  for(int i=0;i<n-1;i++) g<<Q[i].first<<" "<<Q[i].second<<endl;

   return 0;
}