#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,m;		
  for (u=w;t[u]!=u;u=t[u]);
  
  while (t[w]!=w){
    m=t[w];
	t[w]=u;
	w=m;
  }
  
  return u;
}

int ins(long e,long a)
{
  if (r[e]>r[a]) t[a]=e; else
	  t[e]=a;
  if (r[e]==r[a]) ++r[a];
	
  return 0;
}

bool szam()
{
 for (int p=2;p<=n;++p) 
	 if (find(1)!=find(p)) return true;
 
 return false;
}

int krutskal()
{	
  long k=0;  
  meg=0;
  cmin=0;
	
  while (szam()){
    ++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;
}