#include<stdio.h>
#include<algorithm>
#define MAX 200001
using namespace std;
int car[MAX],n,m,T[MAX],R[MAX];
struct muchie
{
	int x,y,c,a;
}v[MAX];
int cmp(muchie a, muchie b)
{
	return (a.c<b.c);
}
void init()
{
	int i;
	for(i=1;i<=n;++i)
	{
		T[i] = i;
		R[i] = 1;
	}
}
void compress(int i,int rad)
{
	int var;
	for(;i!=T[i];i=var)
	{
		var = T[i];
		T[i] = rad;
	}
}
int find(int x)
{
	int i=x;
	for(;i!=T[i];i=T[i]);
	compress(x,i);
	return i;
}
void unite(int x,int y)
{
	if(R[x]>=R[y])
	{
		T[y] = x;
		R[x]+=R[y];
	}
	else
	{
		T[x] = y;
		R[y]+=R[x];
	}
}
int main()
{
	FILE*f = fopen("apm.in","r");
	fscanf(f,"%d%d",&n,&m);
	init();
	int i;
	for(i=1;i<=m;++i)
		fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
	fclose(f);
	
	sort(v+1, v+1+m, cmp);
	
	int cont,p,cost = 0;
	cont = 1;
	for(i=1;i<=m && cont<=n-1;++i)
	{
		if(find(v[i].x) != find(v[i].y))
		{
			v[i].a = 1;
			cost += v[i].c;
			unite(find(v[i].x),find(v[i].y));
			++cont;
		}
	}
	FILE*g=fopen("apm.out","w");
	fprintf(g,"%d\n%d\n",cost,n-1);
	for(i=1;i<=m;++i)
		if(v[i].a)fprintf(g,"%d %d\n",v[i].x, v[i].y);
	fclose(g);
	return 0;
}