#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
	int a,b,c,luat;
};
muchii L[400001];
int maxim(int x,int y)
{
	if(x>y)return x;
	else return y;
}
int cmp(muchii x,muchii y)
{
	return x.c<y.c;
}
int viz[200001],m,n,s,pozmax;
int cauta(int &ok)
{
	int i;
	for(i=1;i<=m;i++)
		if(viz[L[i].a]-viz[L[i].b]==1)
		{	ok=1;return i;}
		else
			if(viz[L[i].b]-viz[L[i].a]==1)
			{ok=0;return i;}
	return 0;
}
int main()
{	
	int poz,i,k,ok;
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>L[i].a>>L[i].b>>L[i].c;
	sort(L+1,L+m+1,cmp);
	viz[L[1].a]=1;
	for(k=1;k<=n-1;k++)
	{
		ok=0;
		poz=cauta(ok);
		if(ok==1)
		{
			viz[L[poz].b]=1;
			s+=L[poz].c;
			L[poz].luat=1;pozmax=max(pozmax,poz);
		}
		else 
		{
			viz[L[poz].a]=1;
			s+=L[poz].c;
			L[poz].luat=1;	pozmax=max(pozmax,poz);
		}
	}
	g<<s<<"\n"<<n-1<<'\n';
	for(i=1;i<=pozmax;i++)
		if(L[i].luat==1)
			g<<L[i].a<<" "<<L[i].b<<'\n';
	return 0;
}