#include<fstream.h>
#define inf 200000
#define infm 400000

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,s,a[inf],c[inf];
struct nod {int e,f,cost;
	    } g[infm];

void citire()
{int i;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 fin>>g[i].e>>g[i].f>>g[i].cost;
 for(i=1;i<=n;i++) c[i]=i;
 }

void afisare()
{int costarb=0,i;

 for(i=1;i<=s;i++)
 costarb+=g[a[i]].cost;

 fout<<costarb<<"\n"<<s<<"\n";
 for(i=1;i<=s;i++)
 {fout<<g[a[i]].e<<" "<<g[a[i]].f;
  fout<<"\n";

  }

 }

int poz(int i,int j)
{int aux,ii=0,jj=-1;
 nod d;

 while(i<j)
 {if(g[i].cost>g[j].cost)
  {d=g[i];
   g[i]=g[j];
   g[j]=d;
   aux=ii;
   ii=-jj;
   jj=-aux;
   }
   i+=ii;
   j+=jj;
  }

 return i;
 }


void quick(int i,int j)
{int k;
 if(i<j)
 {k=poz(i,j);
  quick(i,k-1);
  quick(k+1,j);
  }

 }


int main()
{int i,j,min=0,max=0;
 citire();
 quick(1,m);

 /*for(i=1;i<=m;i++)
 fout<<g[i].cost<<" ";
 fout<<"\n"; */

 for(i=1;s<n-1;i++)
 if(c[g[i].e]!=c[g[i].f])
  {a[++s]=i;
   if(c[g[i].e]<c[g[i].f])
   {min=c[g[i].e];
    max=c[g[i].f];
    }
    else{min=c[g[i].f];
	 max=c[g[i].e];
	 }
   for(j=1;j<=n;j++)
   if(c[j]==max) c[j]=min;

   }

 afisare();
 fin.close();
 fout.close();


 return 0;
 }