#include <stdio.h>
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define nmax 200005
#define inf 500000005
long i, n, m, a, b, c, d[nmax], pozan, rez;
pair<pair<long, long>, long> vfin[nmax];
pair<pair <long, long>, long> el1, el2, el;
vector <pair <pair <long, long>, long> > ma[nmax];
vector <pair<pair <long, long>, long> >::iterator it;
bool fol[nmax];
set <pair<pair<long, long>, long> > v;

void citire()
{
	scanf("%ld %ld",&n, &m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&a, &b, &c);	
		el1.first.second=b;	el1.first.first=c;	el1.second=a;	ma[a].push_back(el1);	
		el2.first.second=a;	el2.first.first=c;	el2.second=b;	ma[b].push_back(el2);	
	}
	for (i=1;i<=n;i++)
		d[i]=inf;
}

void rezolvare()
{
	fol[1]=1;	pozan=1;
	for (i=1;i<=n-1;i++)
	{
		for (it=ma[pozan].begin();it!=ma[pozan].end();it++)
		{
			el=*it;
			if(!fol[el.first.second])
				if (d[el.first.second]>el.first.first)
				{
					if (d[el.first.second]!=inf)
					{	el1.first.second=el.first.second;	el1.first.first=d[el.first.second];	v.erase(el1);	}
					d[el.first.second]=el.first.first;
					v.insert(el);
				}
		}
		el=*v.begin();	v.erase(v.begin());	
		while ((fol[el.first.second])&&(fol[el.second]))
		{	el=*v.begin();	v.erase(v.begin());	}
		vfin[i].first.first=el.first.second;	vfin[i].first.second=el.second; vfin[i].second=el.second%10;
		fol[el.first.second]=1;	rez+=el.first.first;	pozan=el.first.second;
	}
	printf("%ld\n",rez);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	rezolvare();
	printf("%ld\n",n-1);
	for (i=1;i<n;i++)
		printf("%ld %ld\n",vfin[i].first.first,vfin[i].first.second);
	return 0;
}