#include<fstream.h>
#define MMAX 400002
#define NMAX 200002
ifstream in("apm.in");
ofstream out("apm.out");
int x[MMAX],y[MMAX],d[MMAX],m,n,i;
int t[NMAX],rg[NMAX],arb[NMAX];
void quicks(int st,int dr)
{
int sti,dri;
int mij;
int aux;
sti=st;
dri=dr;
mij=d[(st+dr)/2];
do
	{
	while(d[st]<mij) st++;
	while(d[dr]>mij) dr--;
	if(st<=dr)
		{
		aux=d[st];
		d[st]=d[dr];
		d[dr]=aux;

		aux=x[st];
		x[st]=x[dr];
		x[dr]=aux;

		aux=y[st];
		y[st]=y[dr];
		y[dr]=aux;
		st++;
		dr--;
		}
	}while(st<=dr);
if(sti<dr) quicks(sti,dr);
if(dri>st) quicks(st,dri);
}
int rad(int nod)
	{
	while(t[nod]!=nod) nod=t[nod];

	int r=nod;
	int aux;
	while(r!=t[r])
		{
		aux=t[r];
		t[r]=nod;
		r=aux;
		}
	return nod;
	}
void unite(int a,int b)
	{
	if(rg[a]>rg[b]) t[b]=a;
	else t[a]=b;
	if(rg[a]==rg[b]) rg[b]++;
	}
int main(void)
{
int poz;
in>>n>>m;
for(i=1;i<=m;i++)
	in>>x[i]>>y[i]>>d[i];
quicks(1,m);
//for(i=1;i<=m;i++)
  //	out<<x[i]<<" "<<y[i]<<" "<<d[i]<<"\n";

for(i=1;i<=n;i++)
	{
	t[i]=i;
	rg[i]=1;
	}
int suma=0;
poz=1;
for(i=1;i<=n-1;i++)
	{
	while(rad(t[x[poz]])==rad(t[y[poz]])) poz++;
	arb[i]=poz;
	suma+=d[poz];
	unite(rad(t[x[poz]]),rad(t[y[poz]]));
	}
out<<suma<<"\n";
out<<n-1<<"\n";
for(i=1;i<=n-1;i++)
	out<<x[arb[i]]<<" "<<y[arb[i]]<<"\n";
in.close();
out.close();
return 0;
}