// tema8.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
struct set {
	int key;
	int rank;
	set* root;
};

struct edge {
	int u;
	int v;
	int w;	
};

set* make_set(int key) {
	set* s = (set*)calloc(1, sizeof(set));
	s->key = key;
	s->root = s;
	return s;
}

set* find_set(set* s) {
	if (s->root != s) {
		s->root = find_set(s->root);
	}
	return s->root;
}

void union_set(set* s1, set* s2) {
	s1 = find_set(s1);
	s2 = find_set(s2);
	if (s1->rank > s2->rank) {
		s2->root = s1;
		return;
	}
	s1->root = s2;
	if (s1->rank == s2->rank) {
		s2->rank++;
	}
}

int partitieH(edge* g, int l, int h) {
	std::swap(g[(l + h) / 2 + 1], g[l + rand() % (h - l + 1)]);
	int pivot = g[(l + h) / 2 + 1].w;
	l--;
	h++;
	while (true) {
		do {
			l++;
		} while (g[l].w < pivot);

		do {
			h--;
		} while (g[h].w > pivot);

		if (h <= l) {
			return l;
		}
		std::swap(g[l], g[h]);
	}
	return 0;
}

void quickSort(edge* g, int l, int h) {
	if (l >= h) {
		return;
	}
	//std::cout << l << " " << h << "\n";
	int q = partitieH(g, l, h);
	quickSort(g, l, q-1);
	quickSort(g, q, h);
}

edge* MST_KRUSKAL(edge* g, int n, int m, int& w) {
	w = 0;
	set** s = (set**)calloc(n, sizeof(set*));
	for (int i = 0; i < n; i++) {
		s[i] = make_set(i + 1);
	}
	//std::cout << "-2\n";

	quickSort(g, 0, m - 1);

	//std::cout << "-1\n";
	edge* t = (edge*)calloc(n - 1, sizeof(edge));

	int e = 0;

	for (int i = 0; i < m; i++) {
		//std::cout << i << " " << find_set(s[g[i].u])->key << " : " << find_set(s[g[i].v])->key << "\n";
		if (find_set(s[g[i].u - 1])->key != find_set(s[g[i].v-1])->key) {
			//std::cout << e << " ";
			union_set(s[g[i].u-1], s[g[i].v-1]);
			t[e] = g[i];
			w += g[i].w;
			//std::cout << w << "\n";
			e++;
			if (e == n) {
				break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		free(s[i]);
	}
	return t;
}

int main()
{
	int n, m, w;
	fin >> n >> m;
	edge* g = (edge*)calloc(m, sizeof(edge));
	for (int i = 0; i < m; i++) {
		fin >> g[i].u >> g[i].v >> g[i].w;
	}
	edge* t = MST_KRUSKAL(g, n, m, w);
	fout << w << "\n";
	for (int i = 0; i < n - 1; i++) {
		fout << t[i].u << " " << t[i].v << std::endl;
	}
	free(g);
	free(t);
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file