// Arbore partial de cost minim.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("apm.in", "r");
FILE *g=fopen("apm.out", "w");


typedef struct nod
{
	int x, c;
	struct nod*adr;
};

nod *l[200001];

int n, m, nr, sum, nnr;
int heap[200001], poz[200001], vpoz[200001], viz[200001];
int aj[200001], muchii[200001], dl[200001], la[200001];
int md;


void add(int x, int y, int c)
{
	nod *p=new nod;
	p->x=y;
	p->c=c;
	p->adr=l[x];
	l[x]=p;
}


void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y, c;
		fscanf(f, "%d%d%d", &x, &y, &c);
		add(x, y, c);
		add(y, x, c);
	}
}



void upheap(int x)
{
	int fiu=x;
	int tata=x/2;
	while (tata>0 && heap[tata]>heap[fiu])
	{
		int h=heap[tata]; heap[tata]=heap[fiu]; heap[fiu]=h;
		h=poz[tata]; poz[tata]=poz[fiu]; poz[fiu]=h;
		h=muchii[tata]; muchii[tata]=muchii[fiu]; muchii[fiu]=h;
		vpoz[poz[tata]]=tata;
		vpoz[poz[fiu]]=fiu;
		fiu=tata;
		tata=fiu/2;
	}
}


void inheap(int c, int x, int mm)
{
	++nnr;
	heap[nnr]=c;
	poz[nnr]=x;
	muchii[nnr]=1;
	vpoz[x]=nnr;
	upheap(nnr);
}



void initial()
{
	nod *p=l[1];
	while (p!=NULL)
	{
		aj[p->x]=1;
		inheap(p->c, p->x, 1);
		p=p->adr;
	}
	for (int i=2; i<=n; ++i)
		if (aj[i]==0)
			inheap(10000000, i, 1);
	viz[1]=1;
}


void downheap(int x)
{
	int tata=x;
	int fiu=tata*2;
	if (fiu<n-nr && heap[fiu]>heap[fiu+1])
		++fiu;
	while (heap[tata]>heap[fiu] && fiu<n-nr)
	{
		int h=heap[tata]; heap[tata]=heap[fiu]; heap[fiu]=h;
		h=poz[tata]; poz[tata]=poz[fiu]; poz[fiu]=h;
		h=muchii[tata]; muchii[tata]=muchii[fiu]; muchii[fiu]=h;
		vpoz[poz[tata]]=tata;
		vpoz[poz[fiu]]=fiu;
		tata=fiu;
		fiu=tata*2;
		if (fiu<n-nr && heap[fiu]>heap[fiu+1])
			++fiu;
	}
}


int extragemin(int &aux)
{
	dl[++md]=poz[1];
	la[md]=muchii[1];
	muchii[1]=muchii[n-nr];
	aux=poz[1];
	int cv=heap[1];
	heap[1]=heap[n-nr];
	poz[1]=poz[n-nr];
	vpoz[poz[1]]=1;
	poz[n-nr]=0;
	heap[n-nr]=0;
	downheap(1);
	return cv;
}


void inapm(int x)
{
	viz[x]=1;
	nod *p=l[x];
	while (p!=NULL)
	{
		if (!viz[p->x])
		{
			if (heap[vpoz[p->x]]>p->c)
			{
				heap[vpoz[p->x]]=p->c;
				muchii[vpoz[p->x]]=x;
				upheap(vpoz[p->x]);
			}
		}
		p=p->adr;
	}	
}


void program()
{
	for (int i=1; i<=n; ++i)
	{
		int aux;
		++nr;
		sum+=extragemin(aux);
		inapm(aux);
	}
	fprintf(g, "%d\n", sum);
	fprintf(g, "%d\n", n-1);
	for (int j=1; j<md; ++j)
		fprintf(g, "%d %d\n", dl[j], la[j]);
}


int main()
{
	read();
	initial();
	program();
	return 0;
}