#include<fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

void Citire();
void QS(int st,int dr);
void Kruskal();
int find(int x);
int Union(int rad1, int rad2);
void Afisare();
int m,n,cost;
int tata[200009],h[200009];
int contor;

struct muchie
{
	int x;
	int y;
	int c;
};
muchie v[400009],x;

int main()
{
	Citire();
	QS(1,m);
	Kruskal();
	Afisare();
}
void Citire()
{
	int i;
	int xx,yy,cc;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>xx>>yy>>cc;
		v[i].x=xx;
		v[i].y=yy;
		v[i].c=cc;
	}
	//for(i=1;i<=n;i++)
		//tata[i]=-1;//fiecare componenta conexa este independenta
}
void QS(int st,int dr)
{
	if(st<dr)
	{
	int i,j;
	i=st;j=dr;
	muchie z;
	z=v[st];
	while(i<j)
	{
		while(i<j &&v[j].c>=z.c) j--;
		v[i]=v[j];
		while(i<j &&v[i].c<=z.c) i++;
		v[j]=v[i];
	}
	v[i]=z;
	QS(st,i-1);
	QS(i+1,dr);
	}
}
void Kruskal()
{
	int rad1,rad2;
	int i;
	for(i=1;i<=m;i++)
	{
		rad1=find(v[i].x);
		rad2=find(v[i].y);
		if(rad1!=rad2)
		{
			cost+=v[i].c;
			v[i].c=-1;
			contor++;
			Union(rad1,rad2);
		}
	}
}

void Afisare()
{
	int i;
	fout<<cost<<'\n';
	fout<<contor<<'\n';
	for(i=1;i<=m;i++)
		if(v[i].c==-1)
			fout<<v[i].x<<' '<<v[i].y<<'\n';
		
}

int find(int x)
{
	int rad,y;
	rad=x;
	while(tata[rad]!=-1) rad=tata[rad];

	/*while(tata[x]!=rad)
	{
		y=tata[x];
		tata[x]=rad;
		x=y;
	}*/
	return rad;
}
int Union(int rad1,int rad2)
{
	if(h[rad1]<h[rad2])
		tata[rad1]=rad2;
	else 
	{
		tata[rad2]=rad1;
		if(h[rad1]==h[rad2])
			h[rad1]++;
	}
}