#include<fstream.h>
#include<stdlib.h>
#define NM  200001
#define MM  400001
#define endl "\n"
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie{ int x,y,c; };

int n,m,L[NM];

muchie v[MM],h[NM];
void citire()
 { int i;
   in>>n>>m;
   for(i=0;i<m;i++)
		in>>v[i].x>>v[i].y>>v[i].c;
  }
int fcmp(void const*a,void const*b)
  { return ((muchie*)a)->c-((muchie *)b)->c;
   }
int min(int x,int y)
  { if(x<y)  return x;
    return y;
   }
int max(int x,int y)
  { if(x>y) return x;
    return y;
   }
int Find( int x)
  { if(x==L[x]) return x;
    return Find(L[x]);
   }
void Union(int x,int y)
  { int px=Find(x);
    int py=Find(y);
    if(px<py)  L[py]=px;
    else L[px]=py;
   }

int main()
  { int i,ms=0,ct=0,j;
    citire();
    qsort(v,m,sizeof(v[0]),fcmp);
    for(i=1;i<=n;i++) L[i]=i;
    i=0;
    while(ms<n-1)
	  { int px,py;
	    do{ px=Find(v[i].x);
		   py=Find(v[i].y);
		   if(px==py) i++;
		  } while(px===py);
	    h[ms]=v[i];
	    ms++;
	    ct+=v[i].c;
	    int a=max(px,py);
	    int b=min(px,py);
	    Union(b,a);
	  }
    out<<ct<<endl<<n-1<<endl;
   for(i=0;i<n-1;i++)
	  out<<h[i].x<<" "<<h[i].y<<" "<<endl;
   return 0;

 }