#include<fstream>
#define dmax 400004
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n,m,apm[dmax/2],f[dmax/2],h[dmax/2],cst;

struct muchie
{	int a;
	int b;
	short int c;
}	g[dmax];

int sf(struct muchie x,struct muchie y)
{	return x.c < y.c;
}

void uneste(int x,int y)
{	while(f[x])
		x=f[x];
	while(f[y])
		y=f[y];
	
	if(h[x] < h[y])
		f[x]=y;
	else if(h[y] < h[x])
		f[y]=x;
	else if(h[x] == h[y])
	{	f[y]=x;
		h[x]++;
	}	
}

bool cauta(int x,int y)
{	while(f[y])
		y=f[y];
	while(f[x])
		x=f[x];
	
	if(x==y)
		return 1;
	return 0;
}	


void kruskal()
{	int i,nr;

	nr=1;

	for(i=1; i<n ;i++)
	{	while(cauta(g[nr].a,g[nr].b) )
			nr++;
		
		uneste(g[nr].a,g[nr].b);
		cst+=g[nr].c;
		apm[i]=nr;	
	}
	
	out<<cst<<'\n'<<n-1<<'\n';
	for(i=1;i<n;i++)
		out<<g[apm[i]].a<<" "<<g[apm[i]].b<<'\n';
	
}	


int main()
{	int i;
	in>>n>>m;
	for(i=1;i<=m;i++)
		in>>g[i].a>>g[i].b>>g[i].c;
	in.close();
	
	for(i=1;i<=n;i++)
		h[i]=1;
	
	sort( g+1,g+m+1, sf );
	
	kruskal();
	
	out.close();
	return 0;
}