#include<fstream>
#include<list>
#define NMAX 200000
#define INF 2000

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct apm
{
	int v, c;
};
list<apm> a[NMAX];

int i, n, m, d[NMAX], muchie[NMAX], sum, viz[NMAX];

void citire()
{
	int i, x, y, c;
	apm r;
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y>>c;
		r.v=y;r.c=c;a[x].push_back(r);
		r.v=x;a[y].push_back(r);
	}
}

void apm_f()
{
	int i, mn, pzmn, K;
	apm r;
	list<apm> :: iterator it;
	
	for (i=1; i<=n; ++i) d[i]=INF;
	
	for (it=a[1].begin(); it!=a[1].end(); ++it) 
	{
		r=*it;
		d[r.v]=r.c;
		muchie[r.v]=1;
	}
	viz[1]=1;
	for (K=2; K<=n; ++K)
	{
		mn=INF; pzmn=0;
		for (i=1; i<=n; ++i)
			if (d[i]<mn && !viz[i])
			{
				mn=d[i];
				pzmn=i;
			}
		sum+=mn;viz[pzmn]=1;
		for (it=a[pzmn].begin(); it!=a[pzmn].end(); ++it)
		{
			r=*it;
			if (d[r.v]>r.c && !viz[r.v])
			{
				d[r.v]=r.c;
				muchie[r.v]=pzmn;
			}
		}
	}
}
	
void scrie()
{
	int i;
	g<<sum<<"\n"<<n-1<<"\n";
	for (i=2; i<=n; ++i)
		g<<muchie[i]<<" "<<i<<"\n";
}

int main()
{
	citire();
	apm_f();
	scrie();
	f.close();
	g.close();
	return 0;
}