#include <fstream>
#include <vector>
#include <queue>

int N;
std::vector<std::pair<int, int>> G[200001];

int Cost = 0;
std::vector<std::pair<int, int>> Muchii;

int d[200001];

bool InArbore[200001];

struct Compara {
	bool operator()(std::pair<std::pair<int, int>, int>& left, std::pair<std::pair<int, int>, int>& right) const {
		return d[left.first.first] > d[right.first.first];
	}
};

std::priority_queue<std::pair<std::pair<int, int>, int>, std::vector<std::pair<std::pair<int, int>, int>>, Compara> Coada;

#define INF 0x7FFFFFFF;

void Prim(int s) {
	for (int i = 1; i <= N; ++i)
		d[i] = INF;

	d[s] = 0;
	Coada.push({ { s, 0 }, d[s] });

	std::pair<std::pair<int, int>, int> min;

	while (!Coada.empty()) {
		min = Coada.top();

		if (d[min.first.first] != min.second) {
			Coada.pop();

			continue;
		}

		Coada.pop();

		InArbore[min.first.first] = true;

		Cost += min.second;
		Muchii.push_back({ min.first.second, min.first.first });

		for (auto& nod : G[min.first.first]) {
			if (!InArbore[nod.first] && nod.second < d[nod.first]) {
				d[nod.first] = nod.second;

				Coada.push({ { nod.first, min.first.first }, d[nod.first] });
			}
		}
	}

}


int main() {
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");

	int M;

	fin >> N >> M;

	int X, Y, C;

	for (int i = 1; i <= M; ++i) {
		fin >> X >> Y >> C;

		G[X].push_back({ Y, C });
		G[Y].push_back({ X, C });
	}

	fin.close();

	Prim(1);

	fout << Cost << '\n';
	fout << Muchii.size() - 1 << '\n';

	for (int i = 1; i < Muchii.size(); ++i)
		fout << Muchii[i].first << ' ' << Muchii[i].second << '\n';

	fout.close();

	return 0;
}