#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 edge {
	int x, y, cost;
	bool selected;

	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 + 1);

	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;
		edges[i].selected = false;
	}

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

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

			set.merge(muchie.x, muchie.y);
			muchie.selected = true;
		}
	}

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

	for(auto& muchie : edges) if(muchie.selected) std::cout << muchie.x << " " << muchie.y << '\n';
	return 0;
}