#include<iostream>
#include<vector>
#include<utility>
#include<cstdlib>
#include<string>
using namespace std;

struct edge {
    int u, v, c;
};

edge edges[200001];
vector<edge> answer;
int p[200001], size[200001];
int n, m, cost;

int compar(const void *a, const void *b) {
    return (*(edge *)a).c - (*(edge *)b).c;
}

int parent(int x) {
	int par, t;
	par = t = x;
	while(par != p[par]) {
		par = p[par];
	}
	while(x != p[x]) {
		t = p[x];
		p[x] = par;
		x = t;
	}
	return par;
}

void uni(int px, int py) {
	if(size[px] < size[py]) p[px] = py;
	if(size[px] > size[py]) p[py] = px;
	if(size[px] == size[py]) {
		p[px] = py;
		size[py]++;
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int x, y, c, i, px, py;
	scanf("%d %d", &n, &m);
	for(i = 0; i < m; i++) {
		scanf("%d %d %d", &(edges[i].u), &(edges[i].v), &(edges[i].c));
		edges[i].u--, edges[i].v--;
	}
	for(i = 0; i < n; i++) {
		p[i] = i;
		size[i] = 1;
	}
	qsort(edges, m, sizeof(edge), compar);
	for(i = 0; i < m; i++) {
		px = parent(edges[i].u);
		py = parent(edges[i].v);
		if(px != py) {
			uni(px, py);
			cost += edges[i].c;
			answer.push_back(edges[i]);
		}
	}
	printf("%d\n", cost);
	printf("%d\n", answer.size());
	for(vector<edge>::iterator it = answer.begin(); it != answer.end(); ++it) {
		printf("%d %d\n", it->u + 1, it->v + 1);
	}
	return 0;
}