#include <fstream.h>

int n,m;

struct muchie
{
	int x,y,c;
}g[400001];

void citire()
{
	ifstream in("apm.in");
	int i;
	in >>n>>m;
	for(i=1;i<=m;i++) in >>g[i].x>>g[i].y>>g[i].c;
	in.close();
}

int divide(int st,int dr)
{
	int xc=g[st].c,xx=g[st].x,xy=g[st].y;
	while(st<dr)
	{
		while(st<dr && g[dr].c>=xc) dr--;
		g[st].c=g[dr].c;
		g[st].x=g[dr].x;
		g[st].y=g[dr].y;
		while(st<dr && g[st].c<=xc) st++;
		g[dr].c=g[st].c;
		g[dr].x=g[st].x;
		g[dr].y=g[st].y;
	}
	g[st].c=xc;
	g[st].x=xx;
	g[st].y=xy;
	return st;
}

void qsort(int p,int q)
{
	int m=divide(p,q);
	if(m-1>p) qsort(p,m-1);
	if(m+1<q) qsort(m+1,q);
}



int main()
{
	ofstream out("apm.out");
	int c[200001],i,j,NrMSel=0,muchii[200001],cst=0,min,max;
	citire();
	qsort(1,m);
	for(i=1;i<=n;i++) c[i]=i;
	//for(i=1;i<=m;i++)
	//	out <<g[i].c<<" "<<g[i].x<<" "<<g[i].y<<"\n";
	for(i=1;(NrMSel<=n-1 || g[i].c<0) && i<=m;i++)
		if(c[g[i].x]!=c[g[i].y])
		{
			muchii[++NrMSel]=i;
			cst+=g[i].c;
			if(c[g[i].x]>c[g[i].y]) min=c[g[i].y],max=c[g[i].x];
			else min=c[g[i].x],max=c[g[i].y];
			for(j=1;j<=n;j++) if(c[j]==max) c[j]=min;
		}
	out <<cst<<"\n"<<NrMSel<<"\n";	
	for(i=1;i<=NrMSel;i++) out <<g[muchii[i]].x<<" "<<g[muchii[i]].y<<"\n";
	out.close();
}