#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5;

int comp[nmax+5], dim[nmax+5];

int Find(int node) {
	if(comp[node] == node) return node;
	comp[node] = Find(comp[node]);
	return comp[node];
}

void Union(int X, int Y) {
	int rX = Find(X), rY = Find(Y);
	if(dim[rX] < dim[rY]) {
		comp[rX] = rY;
		dim[rY] += dim[rX];
	}
	else {
		comp[rY] = rX;
		dim[rX] += dim[rY];
	}
}

int main() {
	ifstream f("apm.in");
	ofstream g("apm.out");
	
	int n, m; f >> n >> m;
	for(int i=1; i<=n; i++) comp[i] = i, dim[i] = 1;
	set<tuple<int,int,int>> s;
	for(int i=1; i<=m; i++) {
		int x, y, cost; f >> x >> y >> cost;
		s.emplace(cost, x, y);
	}
	int nr = 0;
	int total = 0;
	vector<pair<int,int>> v;
	for(auto i : s) {
		int cost, x, y; tie(cost, x, y) = i;
		if(Find(x) != Find(y)) {
			Union(x, y);
			++nr;
			total += cost;
			v.emplace_back(x, y);
		}
	}
	g << total << "\n" << nr << "\n";
	for(auto i : v) g << i.first << " " << i.second << "\n";
	return 0;
}