#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct node
{ int deg;
  node *father;
} v[200005],*p,*q,*r,*s;

struct link
{ int a,b,val;
} w[400005],*sol[200000];

inline int cmp(link a, link b)
{ return (a.val<b.val); }

int n,m,c,nr;

void reunion(int x, int y)
{ p=&v[x];
  while(p->father) p=p->father;
  q=&v[y];
  while(q->father) q=q->father;
  if(p->deg > q->deg) q->father=p;
	  else if(p->deg < q->deg) p->father=q;
			  else q->father=p, ++p->deg;
}

int que(int x, int y)
{ p=&v[x];
  while(p->father) p=p->father;
  q=&v[y];
  while(q->father) q=q->father;
  r=&v[x];
  while(r!=p) s=r->father, r->father=p, r=s;
  r=&v[y];
  while(r!=q) s=r->father, r->father=q, r=s;
  if(p==q) return 1;
  return 0;
}

int main()
{ int i;
  f>>n>>m;
  for(i=1;i<=m;++i) f>>w[i].a>>w[i].b>>w[i].val;
  sort(w+1,w+m+1,cmp);
  for(i=1;i<=m;++i)
	  if( !que (w[i].a, w[i].b) ) 
		  { c+=w[i].val;
		    sol[++nr]=&w[i];
			reunion(w[i].a, w[i].b);
		  }
  g<<c<<'\n'<<nr<<'\n';
  for(i=1;i<=nr;++i) g<<sol[i]->a<<' '<<sol[i]->b<<'\n';
  f.close(); g.close();
  return 0;
}