#include <stdio.h>
#include <stdlib.h>

#define MAXN 200001
#define MAXM 400001

typedef struct tagVertice{
	int left;
	int right;
	int cost;	
}vertice;

int compare(const void *a, const void *b)
{
	return ((vertice*)a)->cost > ((vertice*)b)->cost;
}

int parent[MAXN];
int height[MAXN];
vertice v[MAXN];

int N,M;

void reunion(int a, int b)
{
	if( height[a] < height[b] ){
		parent[a] = b;
	}
	else{
		parent[b] = a;
		if( height[a] == height[b] )
			height[a]++;
	}
}

int get_root(int a)
{
	int root = a;
	while( parent[root] != root )
		root = parent[root];
	
	parent[a] = root;
	return root;
}

int main(int argc, char* argv[])
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	int i;
	int left,right,cost;
	
	for(i=1;i<=N;i++){
		parent[i]=i;
		height[i]=1;
	}
	
	for(i=0;i<M;i++){
		scanf("%d %d %d",&left,&right,&cost);
		v[i].left = left;
		v[i].right = right;
		v[i].cost = cost;
	}
	
	int muchios=0;
	
	qsort(v,M,sizeof(vertice),compare);
	
	i = 0;
	int j;
	int sum=0;
	while(muchios < (N-1) ){	
		left = v[i].left;
		right = v[i].right;
		cost = v[i].cost;
		
		int rootLeft = get_root(left);
		int rootRight = get_root(right);
		if( rootLeft != rootRight){
			v[muchios].left = left;
			v[muchios].right = right;
			v[muchios].cost = cost;
			sum+=cost;
			muchios++;
			
			reunion(rootLeft,rootRight);
		}
		i++;
	}
	
	printf("%d\n%d\n",sum,N-1);
	for(i=0;i<muchios;i++){
		printf("%d %d\n",v[i].left,v[i].right);
	}
	
	return 0;
}