#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';

		g << V - 2 << '\n';

		parent[source] = 0;
		int i = 1;
		for (it = parent.begin() + 2; it != parent.end(); ++it, ++i)
			g << *it << " " << 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;
}