#include <stdio.h>
#include <algorithm>
#include <string.h>

#define max_n 200000
#define max_m 400000

using namespace std;

int n,m,i,j,x1,y1,c1,cost,rez,k,nr,q;
typedef struct costuri{
	int x,y,c;
};
costuri muchie[max_m];
int T[max_n],rang[max_n];
bool ok[max_n];
int sol[max_m][2];

inline bool cmp(const costuri &a,const costuri &b) {
	return a.c<b.c;
}

inline int multime(int nod) {
	if (T[nod]!=nod) 
		T[nod]=multime(T[nod]);
	return T[nod];
}

void reuneste(int i,int j) {
	i=multime(i);
	j=multime(j);
	if (i==j) return;
	if (rang[i]<rang[j]) 
		T[i]=j;
	else 
		T[j]=i;
	if (rang[i]==rang[j])
		rang[i]++;
}

int main () {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; i++) {
		scanf("%d%d%d",&x1,&y1,&c1);
		muchie[i].c=c1;
		muchie[i].x=x1;
		muchie[i].y=y1;
	}
	
	sort(muchie+1,muchie+m+1,cmp);
	
	for (i=1; i<=n; i++) {
		T[i]=i;
		rang[i]=0;
	}
	
	memset(ok,false,sizeof(ok));
	q=0;
	for (k=1; k<=m; k++) {
		i=muchie[k].x;
		j=muchie[k].y;
		cost=muchie[k].c;
		if (multime(i)!=multime(j)) {
			reuneste(i,j);
			rez+=cost;
			//printf("%d %d %d\n",i,j,cost);
			q++;
			sol[q][0]=i;
			sol[q][1]=j;
		}
	}
	printf("%d\n",rez);
	printf("%d\n",q);
	for (i=1; i<=q; i++)
		printf("%d %d\n",sol[i][0],sol[i][1]);
	return 0;
}