//Arbore partial de cost minim - Algoritmul lui Prim
#include<fstream.h>
#include<stdlib.h>
#define INF 32000

struct vecin_cost
	{long int v;
	 int c;
	 };
vecin_cost *A[200001];
int viz[200001],cmin[200001];
long scmin[200001],cost,n,m,i,k,x,y;

struct muchie
	{long a,b;
	} vm[200001];

int selmin()
{long h=INF,sel;
for(long i=1;i<=n;++i)
	if(!viz[i])
		if(cmin[i]<h) {h=cmin[i];
				sel=i;
				}
return sel;
}

int main()
{ifstream f("apm.in");
ofstream g("apm.out");
f>>n>>m;
for(i=1;i<=n;++i)
	{A[i]=(vecin_cost *)calloc(1,sizeof(vecin_cost));
	A[i][0].v=0;
	cmin[i]=INF;
	}
for(i=1;i<=m;++i)
	{f>>x>>y>>k;
	A[x]=(vecin_cost *)realloc(A[x],(A[x][0].v+2)*sizeof(vecin_cost));
	A[x][++A[x][0].v].v=y;
	A[x][A[x][0].v].c=k;
	A[y]=(vecin_cost *) realloc(A[y], (A[y][0].v+2)*sizeof(vecin_cost));
	A[y][++A[y][0].v].v=x;
	A[y][A[y][0].v].c=k;
	}
viz[1]=1;
for(i=1;i<=A[1][0].v;i++)
	{cmin[A[1][i].v]=A[1][i].c;
	scmin[A[1][i].v]=1;
	}
for(k=2;k<=n;++k)
	{
	x=selmin();
	cost+=cmin[x];
	viz[x]=1;
	vm[++vm[0].a].a=scmin[x];
	vm[vm[0].a].b=x;
	for(i=1;i<=A[x][0].v;++i)
		if(cmin[A[x][i].v]>A[x][i].c) {cmin[A[x][i].v]=A[x][i].c;
						scmin[A[x][i].v]=x;}
	}

g<<cost<<'\n'<<n-1<<'\n';
for(i=1;i<=vm[0].a;++i)
	g<<vm[i].a<<' '<<vm[i].b<<'\n';
f.close();
g.close();
return 0;
}