#include <string>
#include <vector>
#include <fstream>
#include <tuple>
#include <algorithm>

using std::string;
using std::vector;

class Kruskal {
private:
	string input_file;
	string output_file;
	int n, cost;
	vector<std::tuple<int, int, int>> muchii;
	vector<std::pair<int, int>> result;
	int* t;
	int* r;

	void read() {
		std::ifstream in{ input_file, std::ios::in };
		
		int m, x, y, w;
		in >> n >> m;

		t = new int[n + 1];
		r = new int[n + 1];

		for (int i = 1; i <= m; ++i) {
			in >> x >> y >> w;
			muchii.push_back({ w, x, y });
		}

		for (int i = 1; i <= n; ++i) {
			t[i] = i;
			r[i] = 1;
 		}

		in.close();
	}

	int find(int x) {
		if (t[x] == x) {
			return x;
		}
		return t[x] = find(t[x]);
	}

	void unite(int x, int y) {
		if (r[x] > r[y]) {
			t[y] = x;
			r[x] += r[y];
		}
		else {
			t[x] = y;
			r[y] += r[x];
		}
	}

	void solve() {
		std::sort(muchii.begin(), muchii.end());
		
		for (const auto& muchie : muchii) {
			int x = std::get<1>(muchie);
			int y = std::get<2>(muchie);
			int c = std::get<0>(muchie);

			if (find(x) != find(y)) {
				unite(find(x), find(y));
				cost += c;
				result.push_back(std::make_pair(x, y));
			}
		}
	}

public:
	Kruskal(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }, cost{ 0 }{
		read();
		solve();
	};

	void print() {
		std::ofstream out(output_file);

		out << cost << '\n' << result.size() << '\n';
		for (const auto& muchie : result) {
			out << muchie.first << " " << muchie.second << '\n';
		}

		out.close();
	}
};

int main(int argc, char** argv) {
	Kruskal k{ "apm.in", "apm.out" };
	k.print();

	return 0;
}