#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];
long x,y,c,meg,cmin,i;

struct comp
{
  long kezd,veg,cost;
};

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

comp d[sizem];

struct el
{
  long kezd,veg;
};

el elek[sizem];

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)
{
    t[e]=a;

    return 0;
}

int krutskal()
{
  long k=0;
  meg=0;
  cmin=0;

  while (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;
  }
  for (i=m+1;i<=n;++i)
	t[i]=i;

  sort(d+1,d+m+1,compare);

  krutskal();

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

  in.close();
  out.close();

  return 0;
}