#include "bits/stdc++.h"
//#pragma GCC optimize("Ofast")

struct dsu {
	const int len;
	std::vector<int> parent, opt;

	void reset() { 
		parent.resize(len);
		for(int i = 0; i < len; i++) parent[i] = i;

		opt.resize(len); std::fill(opt.begin(), opt.end(), 1);
	}

	dsu(const int n) : len(n) {	reset(); }

	int find(int t) { while(t != parent[t]) t = parent[t] = parent[parent[t]]; return t; }

	void merge(int a, int b) { a = find(a); b = find(b);
		if(a == b) return;

		if(opt[a] < opt[b]) std::swap(a, b);
		parent[b] = a;
		opt[a] += opt[b] == opt[a];
	}

	bool same_set(int a, int b) { return find(a) == find(b); }
};

struct truple {
	int a, b, c;
	bool operator<(const truple& o) const { return a < o.a; }
};
std::istream& operator>>(std::istream& s, truple& t) {
	s >> t.a >> t.b >> t.c;
	return s;
}
std::ostream& operator<<(std::ostream& s, const truple& t) {
	s << t.a << '@' << t.b << '@' << t.c << std::endl;
	return s;
}

struct edge {
	int x, y, cost;

	bool operator<(edge other) {
		return cost < other.cost;
	}
};

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	int n, m; std::cin >> n >> m;
	dsu set(n);

	std::vector<edge> edges(m);
	// for(auto& e : edges) cin >> e.x >> e.y >> e.cost;
	for(int i = 0; i < m; i++) {
		std::cin >> edges[i].x >> edges[i].y >> edges[i].cost;
	}

	std::sort(edges.begin(), edges.end());

	int64_t cost_total = 0;
	std::set<std::pair<int, int>> selected;

	for(auto muchie : edges) {
		if(!set.same_set(muchie.x, muchie.y)) {
			cost_total += muchie.cost;

			set.merge(muchie.x, muchie.y);
			selected.insert({muchie.x, muchie.y});
		}
	}

	std::cout << cost_total << '\n';
	std::cout << n - 1 << '\n';

	for(auto muchie : selected) std::cout << muchie.first << " " << muchie.second << '\n';
	return 0;
}