#include<fstream>
#include<cstdlib>
#include<vector>
using namespace std;

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

edge e[400000];
vector<edge> apm;
int size[200000], par[200000];
ifstream fin("apm.in");
ofstream fout("apm.out");

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

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

bool find(int x, int y) {
	return parent(x) == parent(y);
}

void uni(int x, int y) {
	int px = parent(x);
	int py = parent(y);
	if(size[px] < size[py]) {
		par[px] = py;
		size[py] += size[px];
	} else {
		par[py] = px;
		size[px] += size[py];
	}
}

int main() {
	int i, n, m, cost = 0;
	edge current;
	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> e[i].u >> e[i].v >> e[i].c;
		e[i].u--, e[i].v--;
	}
	for(i = 0; i < n; i++) {
		par[i] = i;
		size[i] = 1;
	}
	qsort(e, m, sizeof(edge), compar);
	for(i = 0; i < m; i++) {
		current = e[i];
		if(!find(current.u, current.v)) {
			apm.push_back(current);
			cost += current.c;
			uni(current.u, current.v);
		}
	}
	fout << cost << "\n";
	fout << apm.size() << "\n";
	for(vector<edge>::iterator it = apm.begin(); it != apm.end(); it++) {
		fout << it->u + 1 << " " << it->v + 1 << "\n";
	}
	return 0;
}