#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

long ul,i,j,k,mmax,nmax,L[200001], nr1, nr2;
long ct;

struct muchii
{
	long x; long y; int c;
} m[400001], final[400001];

bool comparaCost (const muchii &a, const muchii &b)
{
    return a.c < b.c;
}

int main ()
{
	FILE *f,*g;
	f=fopen("kruskal.in", "r");
	g=fopen("kruskal.out", "w");
	fscanf(f, "%d %d", &nmax,&mmax);
	for (i=1; i<=mmax; i++)
	{
		fscanf(f, "%d %d %d", &m[i].x, &m[i].y, &m[i].c);
		if (m[i].x>m[i].y) swap(m[i].x,m[i].y);
	}
	sort(m+1,m+mmax+1, comparaCost);
	for (i=1; i<=nmax; i++) L[i]=i;
	
	ct=0;
	k=0;
	i=1;
	while (k<nmax-1)
	{
		if (L[m[i].x]!=L[m[i].y])
		{
			k++;
			//cout<<m[i].x<<" "<<m[i].y<<"\n";
			final[++ul].x=m[i].x;
			final[ul].y=m[i].y;
			ct+=m[i].c;
			//cout<<"\n";
			for (j=1; j<=nmax; j++) 
			{
				if (L[j]==L[m[i].x]) L[j]=L[m[i].y];
				//cout<<L[j]<<" ";
			}
			//cout<<"\n";
		}
		i++;
	}
	fprintf(g,"%d\n%d\n", ct,nmax-1);
	//for (i=1; i<=mmax; i++) cout<<m[i].x<<" "<<m[i].y<<" "<<m[i].c<<"\n";
	for (i=1; i<=ul; i++) fprintf(g, "%d %d\n", final[i].x,final[i].y);
	fclose(f); fclose(g);
	return 0;
}