#include <stdio.h>
#include <algorithm>
using namespace std;

struct muchie{
    long x,y,c;
};
muchie v[1500];
struct muchii{
    long x,y;
};
muchii w[1500];
long n,i,j,m,k,ct,x,y,l[1500];

void initializare ()
{
    int i;
    for(i=1;i<=n;i++) l[i]=i;
}

void sortare ()
{
    int i,j;
    muchie aux;
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
            if(v[i].c>v[j].c)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
}

int main ()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld %ld", &n, &m);
    for(i=1;i<=m;i++) scanf("%ld %ld %ld", &v[i].x, &v[i].y, &v[i].c);
    sortare ();
    initializare();
    i=0;j=0;k=0; ct=0;
	while(k<n-1)
	{
		if(l[v[i].x]!=l[v[i].y])
		{
			k++;ct=ct+v[i].c;
			w[i].x=v[i].x; w[i].y=v[i].y;
			x=l[v[i].y];
			y=l[v[i].x];
			for(j=1;j<=n;j++)
				if(l[j]==x) l[j]=y;
		}
		i++;
	}
    printf("%ld\n%ld\n", ct, k);
    for(i=1;i<=n-1;i++) printf("%ld %ld\n", w[i].y, w[i].x);
    return 0;
}