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


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

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

	void read() {
		std::ifstream in(input_file);

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

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

		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]) {
			r[x] += r[y];
			t[y] = x;
			return;
		}

		r[y] += r[x];
		t[x] = y;
	}

	void solve() {
		std::sort(muchii.begin(), muchii.end(), [](auto& m1, auto& m2) {
			return std::get<2>(m1) < std::get<2>(m2);
			});

		for (const auto& muchie : muchii) {
			if (find(std::get<0>(muchie)) != find(std::get<1>(muchie))) {
				unite(find(std::get<0>(muchie)), find(std::get<1>(muchie)));
				cost += std::get<2>(muchie);

				result.push_back(std::make_pair(std::get<0>(muchie), std::get<1>(muchie)));
			}
		}
	}

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';
		out << result.size() << '\n';
		for (const auto& muchie : result) {
			out << muchie.first << " " << muchie.second << '\n';
		}

		out.close();
	}

	~Kruskal() {
		free(t);
		free(r);
	}
};

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