#include<cstdio>
#include<algorithm>
#include<stdlib.h>
using namespace std;
struct MUCHIE {
	long x,y,c;
	bool ok;
};
MUCHIE w[400001];
long t[200001];
long h[200001];
long n,m,i;
void read () {
	long i;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;i++)
		scanf("%ld%ld%ld",&w[i].x,&w[i].y,&w[i].c);
}

long find (long x) {
	long y,r;
	for (r=x;t[r]!=r;r=t[r]);
	while (t[x]!=x) {
		y=t[x];
		t[x]=r;
		x=y;
	}
	return r;
}

void Union (long x, long y) {
	if (h[x]>h[y])
		t[y]=x;
	else
		if (h[y]>h[x])
			t[x]=y;
		else
			if (h[y]==h[x]) {
				h[x]++;
				t[y]=x;
			}
}

int cmp(const void *a,const void *b){
	MUCHIE *pa,*pb;
	pa=(MUCHIE*)a;
	pb=(MUCHIE*)b;
	return pa->c-pb->c;
}

void solve () {
	long i,s=0,num=0,rx,ry,u=0;
	qsort(w+1,m,sizeof (w[0]),cmp);
	for (i=1;i<=n;i++)
		t[i]=i;
	for (i=1;num<n-1;i++) {
		rx=find(w[i].x);
		ry=find(w[i].y);
		if (rx!=ry) {
			s=s+w[i].c;
			num++;
			Union(rx,ry);
			w[i].ok=1;
		}
	}
	printf("%ld\n%ld\n",s,n-1);
	for (i=1;i<=m;i++)
		if (w[i].ok==1)
			printf("%ld %ld\n",w[i].y,w[i].x);
}

int main () {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	read ();
	solve ();
	return 0;
}