#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie
{
    int x,y,c;
}u[200001];

int n,m,t[200001],ct,h[200001],sol[200001];

int compare (Muchie a,Muchie b)
{
    return(a.c<b.c);
}

int muchie (int X,int Y)
{
  int r1,r2,C,x1,y1;
  r1=X;
  r2=Y;
  while(r1!=t[r1]){r1=t[r1];}
  while(r2!=t[r2]){r2=t[r2];}


  if(r1==r2)return 0;
  while(t[X]!=r1)
  {
       x1=t[X];
       t[X]=r1;
       X=x1;
  }

  while(t[Y]!=r2)
  {
      y1=t[Y];
      t[Y]=r2;
      Y=y1;
  }

   if(h[r1]>h[r2]){t[r2]=r1;C=r1;}
   else {t[r1]=r2;C=r2;}
   if(h[r1]==h[r2]){h[C]++;}

  return 1;

}


void kruskal()
{
   int k,i;
   k=0;
   i=1;

   while(k<n-1)
   {
       if(muchie(u[i].x,u[i].y))
       {
           ct+=u[i].c;
           sol[++k]=i;
       }
       i++;
   }
}


int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        h[i]=1;
        t[i]=i;
    }
    for(i=1;i<=m;i++)
    {
        f>>u[i].x>>u[i].y>>u[i].c;

    }

    sort(u+1,u+m+1,compare);
    kruskal();
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        g<<u[sol[i]].x<<" "<<u[sol[i]].y<<'\n';
    }
    return 0;
}