#include <iostream>
#include <fstream>
#include <vector>
std::ifstream f("apm.in");
std::ofstream g("apm.out");
struct SetNode {
	int data;
	int rank;
	SetNode *parent;
};
class HashMap {
private:
	struct HashNode {
		SetNode*value;
		HashNode*next;
	};
	HashNode **table;
	int capacity;

	int getHashKey(int value) {
		return value % capacity;
	}

public:
	HashMap(int capacity) {
		this->capacity = capacity;
		table = new HashNode*[capacity];
		for (int i = 0; i < capacity; ++i)
			table[i] = NULL;
	}

	void insert(int key, SetNode* value) {
		key = getHashKey(key);

		HashNode*t = new HashNode;
		t->value = value;
		t->next = NULL;

		if (table[key] == NULL) {
			table[key] = t;
			return;
		}

		HashNode* q;
		for (q = table[key]; q->next; q = q->next)
			if (q->value == value)
				return;
		if (q->value == value)
			return;

		q->next = t;
	}

	SetNode* getData(int data) {
		int key = getHashKey(data);

		if (table[key] == NULL)
			return NULL;

		for (HashNode*q = table[key]; q; q = q->next)
			if (q->value->data == data)
				return q->value;
		return NULL;
	}	
};
class DisjointSet {
private:
	HashMap* h;

	void makeSet(int data) {
		SetNode* t = new SetNode;
		t->data = data;
		t->rank = 0;
		t->parent = t;
		h->insert(data, t);
	}

	SetNode* findSet(SetNode* node) {
		if (node == node->parent)
			return node->parent;
		return node->parent = findSet(node->parent);
	}

public:
	DisjointSet(int capacity) {
		h = new HashMap(capacity);
		for (int i = 1; i <= capacity; ++i) {
			makeSet(i);
		}
	}

	bool union1(int data1, int data2) {
		SetNode* node1 = h->getData(data1);
		SetNode* node2 = h->getData(data2);

		SetNode* parent1 = findSet(node1);
		SetNode* parent2 = findSet(node2);

		if (parent1->data == parent2->data)
			return false;

		if (parent1->rank >= parent2->rank) {
			parent1->rank = (parent1->rank == parent2->rank) ? parent1->rank + 1 : parent1->rank;
			parent2->parent = parent1;
		}
		else {
			parent1->parent = parent2;
		}

		return true;
	}
};
///Vector for edges
struct edge {
	int x, y;
	int cost;
};
std::vector<edge> v;
///End of vector for edges

///Begin of quickSort
int partition(int left, int right) {
	int i = left;
	int j = right;
	int pivot = v[(left + right) / 2].cost;

	while (i <= j) {
		while (v[i].cost < pivot)
			++i;
		while (v[j].cost > pivot)
			--j;
		if (i <= j) {
			std::swap(v[i], v[j]);
			++i;
			--j;
		}
	}

	return i;
}
void quickSort(int left, int right) {
	int index = partition(left, right);
	if (left < index - 1)
		quickSort(left, index - 1);
	if (index < right)
		quickSort(index, right);
}
///End of quickSort

///Vector for solution
struct edgeSol {
	int x, y;
};
std::vector<edgeSol> sol;
///End of vector for solution
int main() {
	int n;
	f >> n;

	int m;
	f >> m;

	v.reserve(m + 1);

	edge k;
	k.x = k.y = k.cost = -1001;
	v.push_back(k);

	for (int i = 1; i <= m; ++i) {
		f >> k.x >> k.y >> k.cost;
		v.push_back(k);
	}

	quickSort(1, m);

	DisjointSet* set = new DisjointSet(n);

	int i = 1;
	int nr = 0;
	int nrMin = n - 1;
	int sum = 0;

	while (nr < nrMin) {
		if (set->union1(v[i].x, v[i].y)) {
			sol.push_back({ v[i].x, v[i].y });
			sum += v[i].cost;
			++nr;
		}
		++i;
	}

	g << sum << '\n';

	int sz = sol.size();
	g << sz << '\n';

	for (int i = 0; i < sz; ++i) {
		g << sol[i].x << " " << sol[i].y << '\n';
	}

	return 0;
}