#include<fstream>
#include<algorithm>
#define MMAX 400005
#define NMAX 200005

using namespace std;

struct muchie
	{int x;int y;int c;} a[MMAX];
	
int k,i,n,m,viz[MMAX],x,y,h[NMAX],s,j;

int cmp(muchie x, muchie y)
{
	if (x.c<y.c) return 1;
	return 0;
}

int main()
{
	ifstream f("grader_test1.in");
	ofstream g("apm.out");
	
	f>>n>>m;
	for (i=1;i<=m;i++) f>>a[i].x>>a[i].y>>a[i].c;
	
	sort(a+1, a+m+1, cmp);
	
	for (i=1;i<=n;i++) h[i]=i;
	
	s=0;i=1;k=0;
	while (k<n-1)
	{
		if (h[a[i].x]!=h[a[i].y])
		{
			x=h[a[i].x];
			y=h[a[i].y];
			for (j=1;j<=n;j++)
				if (h[j]==y) h[j]=x;
			viz[i]=1;
			s+=a[i].c;
			k++;
		}
		i++;
	}
	
	g<<s<<"\n"<<n-1<<"\n";
	for (i=1;i<=m;i++)
		if (viz[i]) g<<a[i].x<<" "<<a[i].y<<"\n";
	
	f.close();
	g.close();
	return 0;
}