#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,ct,k,nr1,nr2,j,l[400001];
struct muchie
{
	int x,y,c;
}u[400001],sol[400001];
bool cmp(muchie a, muchie b)
{
	return a.c<b.c;
}
int main() 
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>u[i].x>>u[i].y>>u[i].c;
		l[i]=i;
	}
	sort(u+1,u+m+1,cmp);
	k=0;i=1;ct=0;
	while(k<n-1)
	{
		if(l[u[i].x]!=l[u[i].y])
		{
			++k;
			sol[k]=u[i];
			ct=ct+u[i].c;
			nr1=l[u[i].x];
			nr2=l[u[i].y]; 
			for (j=1;j<=n;++j) 
				if (l[j]==nr2) l[j]=nr1; 
		}
		++i;
	}
	g<<ct<<'\n';
	g<<k<<'\n';
	for(i=1;i<=k;++i)
	{
		g<<sol[i].x<<' '<<sol[i].y<<'\n';
	}
	return 0;
}