#include <cstdio>
#include <list>
using namespace std;

#define MAXN 200000
#define MAXM 400000

struct edge {
	int from;
	int to;
	int cost;
};
struct disjoint_set {
	int parent[MAXN+1];
	int size[MAXN+1];
};

int N, M;
edge edges[MAXM+1];
disjoint_set set;

void readInput() {	
	freopen("apm.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (int i=1;i<=M;i++) {
		scanf("%d %d %d",&edges[i].from,&edges[i].to,&edges[i].cost);
	}
}

void max_heapify(int i, int size) {
	int largest = i;
	int left = i << 1;
	int right = left + 1;
	if (left <= size && edges[left].cost > edges[largest].cost) {
		largest = left;
	}
	if (right <= size && edges[right].cost > edges[largest].cost) {
		largest = right;
	}
	if (largest != i) {
		swap(edges[i], edges[largest]);
		max_heapify(largest, size);
	}
}

void heapSortEdges() {
	int size = M;
	for (int i=M/2;i>=1;i--)
		max_heapify(i,size);	
	while (size > 1) {
		swap(edges[1],edges[size]);
		size--;
		max_heapify(1, size);
	}
}

int get_set_representative(int x) {
	while (set.parent[x] != x) {
		x = set.parent[x];
	}
	return x;
}

void union_sets(int r1, int r2) {
	if (set.size[r1] >= set.size[r2]) {
		set.size[r1] += set.size[r2];
		set.parent[r2] = r1;
	}
	else {
		set.size[r2] += set.size[r1];
		set.parent[r1] = r2;
	}
}

int main() {
	int r1, r2, tree_cost=0, tree_size=0;
	list<edge> solution;
	readInput();
	for (int i=1;i<=N;i++) {
		set.parent[i] = i;
		set.size[i] = 1;
	}
	heapSortEdges();
	for (int i=1;i<=M && tree_size < N-1;i++) {
		r1 = get_set_representative(edges[i].from);
		r2 = get_set_representative(edges[i].to);
		if ( r1 != r2) {			
			tree_cost += edges[i].cost;
			tree_size++;
			solution.push_back(edges[i]);
			union_sets(r1,r2);
		}		
	}
	freopen("apm.out","w",stdout);
	printf("%d\n%d\n",tree_cost,tree_size);
	while (!solution.empty()) {
		printf("%d %d\n", solution.front().from, solution.front().to);
		solution.pop_front();
	}
	return 0;
}