#include <fstream>
#include <algorithm>
#define sizem 400010
#define sizen 200010

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
long n,m,t[sizen],r[sizen];
long x,y,c,meg,cmin,i;

struct comp
{
  long kezd,veg,cost;

  bool operator<(const comp &a) { return (cost<a.cost); }
  
};

inline bool compare(comp a,comp b) 
{ return(a<b);}

comp d[sizem];

struct el
{
  long kezd,veg;	
};

el elek[sizem];

int writeout()
{
  out << cmin << "\n";
  out << meg << "\n";
  for (int o=1;o<=meg;++o) out << elek[o].kezd << " " << elek[o].veg << "\n";
	
  return 0;
}

long find(long w)
{
  long u;		
  for (u=w;t[u]!=u;u=t[u]);
  
  return u;
}

int ins(long e,long a)
{
  t[e]=a;
	
  return 0;
}

int krutskal()
{	
  long k;  
  meg=0;
  cmin=0;
	
  for (k=1;k<=m;++k){
	if (find(d[k].kezd)!=find(d[k].veg)){
	  ins(find(d[k].kezd),find(d[k].veg));	
	  
	  elek[++meg]=(el){d[k].kezd,d[k].veg};
	  cmin+=d[k].cost;
	}
  
  }

  return 0;
}

int main()
{
  in >> n >> m;
  for (i=1;i<=m;++i){
    in >> x >> y >> c;
	d[i]=(comp){x,y,c};     
	t[i]=i;
	r[i]=1;
  }
  for (i=m+1;i<=n;++i){
	t[i]=i;
	r[i]=1;
  }
  
  sort(d+1,d+m+1,compare);
  
  krutskal();
  
  writeout();
	
  in.close();
  out.close();  

  return 0;
}