#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
typedef struct nod{int cost, la; nod *urm;}NOD;
NOD *p[200005];
typedef struct rez{int x, y;}REZ;
REZ rezult[200005];
int muchii[200005];
int n,m,viz[200005],s;
void insert (int x, int y, int c)
{
	nod *q=new nod;
	q->cost=c;
	q->la=y;
	q->urm=p[x];
	p[x]=q;
	nod *r=new nod;
	r->cost=c;
	r->la=x;
	r->urm=p[y];
	p[y]=r;
}
void citire()
{
	f>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y,c;
		f>>x>>y>>c;
		insert(x,y,c);
	}
}
int INF=999999999;
void prim()
{
	viz[1]=1;
	muchii[1]=1;
	for (int i=2;i<=n;i++)
	{
		int min=INF;
		int poz,raz;
		for (int j=1;j<=i;j++)
			for (nod *q=p[muchii[j]];q;q=q->urm)
				if (q->cost<min&&viz[q->la]==0){ min=q->cost;poz=q->la;raz=muchii[j];}
		s+=min;
		muchii[i]=poz;
		viz[poz]=1;
		rezult[i].x=raz;
		rezult[i].y=poz;
	}
	g<<s<<'\n'<<n-1<<'\n';
	for (int i=2;i<=n;i++)
		g<<rezult[i].x<<' '<<rezult[i].y<<'\n';
}
int main()
{
	citire();
	prim();
	return 0;
}