#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "apm.in"
#define file_out "apm.out"

#define nmax 501010


int x[nmax];
int y[nmax];
int c[nmax];

int N,M;
int i,j,t1,t2;
int tata[nmax];
int ind[nmax];
int sol[nmax];
int nr=0;
int cost;

int cmp(int a, int b){
	
	return (c[a]<c[b]);
}


int find(int x){
	
	if (x!=tata[x])
		tata[x]=find(tata[x]);
	return tata[x];
}

void unite(int i, int j){
	
	tata[i]=j;
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	for (i=1;i<=M;++i){
		 scanf("%d %d %d", &x[i], &y[i],&c[i]);
		 ind[i]=i;
	}
	for (i=1;i<=M;++i) tata[i]=i;
	
	sort(ind+1,ind+M+1,cmp);
	
	for (i=1;i<=M;++i){
		
		t1=find(x[ind[i]]);
		t2=find(y[ind[i]]);
		if (t1!=t2){
			unite(t1,t2);
			cost+=c[ind[i]];
			sol[++nr]=ind[i];
		}
		
	}
	
	printf("%d\n", cost);
	printf("%d\n", nr);
	for (i=1;i<=nr;++i)
		 printf("%d %d\n", x[sol[i]],y[sol[i]]);
	
	return 0;
	
}