#include<stdio.h>
#define MAX 200001
int car[MAX],n,m,size = 0,cont,cost;
struct muchie
{
	int x,y,c;
}v[MAX],aux,vec[MAX];
int father(int x)
{
	return x/2;
}
int left_son(int x)
{
	return 2*x;
}
int right_son(int x)
{
	return 2*x+1;
}
void sift(int x)
{
	int son;
	do
	{
		if(left_son(x) <=size)
		{
			son = left_son(x);
			if(right_son(x) <= size && v[son].c > v[right_son(x)].c)
				son = right_son(x);
		}
		if(v[son].c >= v[x].c)
			son = 0;
		if(son)
		{
			aux = v[son];
			v[son] = v[x];
			v[x] = aux;
			x = son;
		}
	}while(son);
}
void percolate(int x)
{
	while(father(x) && v[father(x)].c > v[x].c)
	{
		aux = v[x];
		v[x] = v[father(x)];
		v[father(x)] = aux;
		
		x=father(x);
	}
}
void add(muchie var)
{
	v[++size] = var;
	percolate(size);
}
void cut(int x,int del)
{
	aux = v[x];
	v[x] = v[size];
	v[size] = aux;
	
	if(del)--size;
	
	if(v[father(x)].c > v[x].c)
	{
		percolate(x);
	}
	else sift(x);
}
int main()
{
	FILE*f = fopen("apm.in","r");
	fscanf(f,"%d%d",&n,&m);
	int i;
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&aux.x,&aux.y,&aux.c);
		add(aux);
	}
	fclose(f);
	cont = 1;
	while(cont<=n-1)
	{
		car[v[1].x] = car[v[1].y] = 1;
		cost+=v[1].c;
		vec[cont] = v[1];
		if(cont == n-1){++cont;continue;}
		cut(1,1);
		while(!( (!car[v[1].x] || !car[v[1].y]) && (car[v[1].x] || car[v[1].y]) ))
		{
			if(car[v[1].x] && car[v[1].y])
			cut(1,1);	
			else cut(1,0);
		}
		
		++cont;
	}
	FILE*g=fopen("apm.out","w");
	fprintf(g,"%d\n%d\n",cost,n-1);
	
	for(i=1;i<cont;++i)
		fprintf(g,"%d %d\n",vec[i].x, vec[i].y);
	
	fclose(g);
	return 0;
}