#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 1<<30
 
std::ifstream f("apm.in");
std::ofstream g("apm.out");
 
#define makeNode(a,b) std::make_pair(a, b)
typedef std::pair<int, int> Node;
 
class Graph {
private:
	int V; // No. of vertices
	std::vector<Node> *table;
 
public:
	Graph(int V) {
		this->V = V;
		table = new std::vector<Node>[V];
	}
 
	void addEdge(int x, int y, int cost) {
		table[x].push_back(makeNode(y, cost));
		table[y].push_back(makeNode(x, cost));
	}
 
	void primMST(int source) {
 
		std::priority_queue< Node, std::vector<Node>, std::greater<Node> > h;
 
		std::vector<int> costs(V, INF);
		std::vector<int> parent(V, -1);
		std::vector<bool> inMST(V, false);
 
		h.push(makeNode(0, source));
		costs[source] = 0;
 
		while (!h.empty()) {
 
			int currentVertex = h.top().second;
			h.pop();
 
			inMST[currentVertex] = true;
 
			std::vector<Node>::iterator it;
			for (it = table[currentVertex].begin(); it != table[currentVertex].end(); ++it) {
				int vertex = it->first;
				int cost = it->second;
 
				if (!inMST[vertex] && costs[vertex] > cost) {
					costs[vertex] = cost;
					h.push(makeNode(cost, vertex));
					parent[vertex] = currentVertex;
				}
			}
 
		}
 
		int sum = 0;
		std::vector<int>::iterator it;
		for (it = costs.begin() + 1; it != costs.end(); ++it)
			sum += *it;
		g << sum << '\n';
		
		int n = V - 2;
		g << n << '\n';

		++n;
		parent[source] = -1;
		for (int i = 1; i <= n; ++i) {
			if (parent[i] != -1)
				g << i << " " << parent[i] << '\n';
		}
		g << '\n';
	}
 
};
 
int main() {
	int n;
	f >> n;
 
	Graph* myGraph = new Graph(n + 1);
 
	int m;
	f >> m;
 
	int x, y, cost;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y >> cost;
		myGraph->addEdge(x, y, cost);
	}
 
	myGraph->primMST(1);
 
	return 0;
}