#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <fstream>
#include <utility>
#include <functional>

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

struct Edge {
	int cost, from, to;
	Edge(int cost, int from, int to) {
		this->cost = cost;
		this->to = to;
		this->from = from;
	}
	friend bool operator<(const Edge& l, const Edge& r) {
		return l.cost < r.cost;
	}
	friend bool operator>(const Edge& l, const Edge& r) {
		return l.cost > r.cost;
	}
};

class Graph {
private:
	std::vector<std::vector<Edge> > graphMap;
public:
	Graph();
	Graph(int);
	~Graph();
	void addNode();
	void pushVertex(const Edge);
	std::vector<Edge> getMST();
};


int main() {
	int N, M;

	fin >> N >> M;

	Graph *graph = new Graph(N);

	for (int i = 0; i < M; i++) {
		int a, b, c;
		fin >> a >> b >> c;
		graph->pushVertex(Edge(c, a - 1, b - 1));
	}

	std::vector<Edge> rs = graph->getMST();

	int sum = 0;
	for (std::vector<Edge>::iterator it = rs.begin(); it != rs.end(); it++) {
		sum += it->cost;
	}

	fout << sum << "\n" << rs.size() << "\n";
	for (std::vector<Edge>::iterator it = rs.begin(); it != rs.end(); it++) {
		fout << it->from + 1 << " " << it->to + 1 << "\n";
	}

	return 0;
}



Graph::Graph() {}

Graph::Graph(int nodes) {
	for (int i = 0; i < nodes; i++) {
		this->addNode();
	}
}

Graph::~Graph() {}

void Graph::addNode() {
	this->graphMap.push_back(std::vector<Edge>());
}

void Graph::pushVertex(const Edge edge) {
	this->graphMap[edge.from].push_back(edge);
	this->graphMap[edge.to].push_back(edge);
}

std::vector<Edge> Graph::getMST() {
	unsigned int processedCount = 0;
	unsigned int N = this->graphMap.size();
	bool *processedMap = new bool[N]();
	unsigned int front = 0;
	std::priority_queue < Edge, std::vector<Edge>, std::greater<Edge> > edges;

	std::vector<Edge> temp;

	while (processedCount < N) {
		processedMap[front] = true;
		processedCount++;

		for (std::vector<Edge>::iterator it = this->graphMap[front].begin(); it != this->graphMap[front].end(); it++) {
			if (!processedMap[it->from] || !processedMap[it->to]) {
				edges.push(*it);
			}
		}

		while (!edges.empty()) {
			Edge smallestEdge = edges.top();
			edges.pop();
			if (!processedMap[smallestEdge.from]) {
				front = smallestEdge.from;
				temp.push_back(smallestEdge);
				break;
			}
			else if (!processedMap[smallestEdge.to]) {
				front = smallestEdge.to;
				temp.push_back(smallestEdge);
				break;
			}
		}
	}
	return temp;
}