#include<stdio.h>
#include<vector>
#include<set>
#include<utility>
#define inf 2000
#define nmax 200005
using namespace std;
struct vecin{long n, c;};
long a, b, c, n, m, poz, rez, i;
vector <vecin> ma[nmax];
vector <vecin> ::iterator it;
set < pair < long, long> > h;
pair < long, long > mchal;
vecin el, mch, cmin[nmax];
bool fol[nmax];

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

void rezolvare()
{
	fol[1]=1;	poz=1;
	for (i=1;i<=n-1;i++)
	{
		for (it=ma[poz].begin();it!=ma[poz].end();it++)
		{
			mch=(*it);
			if (!fol[mch.n])
				if (cmin[mch.n].c>mch.c)
				{
					if(cmin[mch.n].c!=inf)
						h.erase(make_pair(cmin[mch.n].c,mch.n));
					cmin[mch.n].c=mch.c;	cmin[mch.n].n=poz;
					h.insert(make_pair(mch.c,mch.n));
				}
		}	
			while ( (fol[(*h.begin()).second]) && (fol[cmin[(*h.begin()).second].n]) )	
				h.erase(h.begin());
			mchal=*h.begin();
			if(fol[mchal.second])
			{	poz=cmin[mchal.second].n;	fol[cmin[mchal.second].n]=1;	}
			else
			{	poz=mchal.second;		fol[mchal.second]=1; }
			h.erase(h.begin());
			rez+=mchal.first;
	}
}

void afisare()
{
	printf("%ld\n",rez);
	printf("%ld\n",n-1);
	for (i=2;i<=n;i++)
		printf("%ld %ld\n",cmin[i].n, i);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	for (i=1;i<=n;i++)
		cmin[i].c=inf;
	rezolvare();
	afisare();
	return 0;
}