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

ifstream fin("apm.in");
ofstream fout("apm.out");

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

edge muchii[400000];
vector<edge> arb;
int par[200001], size[200001];

void init(int n) {
	for(int i = 1; i <= n; i++) {
		par[i] = i;
		size[i] = 1;
	}
}

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

void nodes_union(int u, int v) {
	int pu = parent(u), pv = parent(v);
	if(size[pu] > size[pv]) par[pv] = pu;
	if(size[pu] < size[pv]) par[pu] = pv;
	if(size[pu] == size[pv]) {
		par[pv] = pu;
		size[pu]++;
	}
}

bool nodes_find(int u, int v) {
	return parent(u) == parent(v);
}

int compar(const void *m1, const void *m2) {
	return (*(edge *)m1).cost - (*(edge *)m2).cost;
}

int main() {
	int i, n, m, cost = 0;
	fin >> n >> m;
	init(n);
	for(i = 0; i < m; i++) fin >> muchii[i].u >> muchii[i].v >> muchii[i].cost;
	qsort(muchii, m, sizeof(edge), compar);
	for(i = 0; i < m; i++) {
		if(nodes_find(muchii[i].u, muchii[i].v) == false) {
			arb.push_back(muchii[i]);
			cost += muchii[i].cost;
			nodes_union(muchii[i].u, muchii[i].v);
		}
	}
	fout << cost << "\n" << n-1 << "\n";
	for(vector<edge>::iterator it = arb.begin(); it != arb.end(); ++it) {
		fout << (*it).u << " " << (*it).v << "\n";
	}
	return 0;
}