#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,n,m,tata[200001],adanc[200001],sum,radx,rady,nr;
struct muchii
{
	int x,y,c,luat;
};
muchii L[400001];
int cmp(muchii a,muchii b)
{
	return a.c<b.c;
}
void citire()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>L[i].x>>L[i].y>>L[i].c;
	
}
int rad(int i)
{
	while(tata[i]!=i)
		i=tata[i];
	return i;
}
void uneste(int x,int y)
{
	
	if(adanc[x]==adanc[y])
		{tata[x]=y;adanc[y]++;}
	else if(adanc[x]>adanc[y])
			tata[y]=x;
		else tata[x]=y;
			
}
void kruskal()
{
	for(i=1;i<=m&&nr<n-1;i++)
	{
		radx=rad(L[i].x);
		rady=rad(L[i].y);
		if(radx!=rady)
		{
			uneste(radx,rady);
			sum+=L[i].c;
			L[i].luat=1;nr++;
			
		}
	}
}
void afisare()
{
	g<<sum<<'\n';
	g<<n-1<<'\n';
	for(i=1;i<=m;i++)
		if(L[i].luat)
			g<<L[i].x<<" "<<L[i].y<<'\n';
}
int main()
{
	citire();
	sort(L+1,L+m+1,cmp);
	for(i=1;i<=n;i++)tata[i]=i;
	kruskal();
	afisare();
	return 0;
}