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

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

int cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

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

void citire ()
{
   	int i=0,x,y,c;
   	scanf("%d %d\n", &n, &m);
	for (i=1;i<=m;++i)
	{
        scanf("%d %d %d\n", &x, &y, &c);
		v[i].x=x;v[i].y=y;
		v[i].c=c;
	}
}

int main ()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire ();
    sort(v+1,v+m+1,cmp);
    initializare();
    i=0;j=0;k=0; ct=0; q=0;
	while(k<n-1)
	{
		if(l[v[i].x]!=l[v[i].y])
		{
			k++;
			ct=ct+v[i].c;
			w[++q].x=v[i].x; w[q].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("%d\n%d\n", ct, k);
    for(i=1;i<=q;i++) printf("%d %d\n", w[i].y, w[i].x);
    return 0;
}