#include <fstream>
#include <vector>
#include <set>

#define INFINITY 10002

int n, m;
std::vector<std::vector<std::pair<int,int>>> graph;

void Prim() {
	std::vector<std::pair<int,int>> edges;
	std::vector<int>parent(n + 1);
	std::set< std::pair<int,int> > cost;
	std::vector<std::pair<int,int>> mstSet;
	std::vector<bool>visited(n + 1, false);
	std::vector<int>cost_list(n + 1, INFINITY);

	parent[1] = 0;
	cost_list[1] = 0;
	cost.insert(std::make_pair(0, 1));

	for (int i = 2; i <= n; i++) 
		cost.insert(std::make_pair(INFINITY, i));

	while (!cost.empty()) {
		std::pair<int,int> top = *cost.begin();
		cost.erase(cost.begin());
		mstSet.push_back(top);
		visited[top.second] = true;

		for (int i = 0; i < graph[top.second].size(); i++) {
			if (!visited[graph[top.second][i].first] && cost_list[graph[top.second][i].first] > graph[top.second][i].second) {
				cost.erase(std::make_pair(cost_list[graph[top.second][i].first], graph[top.second][i].first));
				cost_list[graph[top.second][i].first] = graph[top.second][i].second;
				cost.insert(std::make_pair(cost_list[graph[top.second][i].first], graph[top.second][i].first));
				parent[graph[top.second][i].first] = top.second;
			}
		}
	}

	int total_cost = mstSet[0].first;
	for (int i = 1; i < n; i++) {
		total_cost += mstSet[i].first;
		edges.push_back(std::make_pair(parent[i + 1], i + 1));
	}

	std::ofstream fout("apm.out", std::ofstream::out);
	
	fout << total_cost << '\n';
	fout << edges.size() << '\n';
	for (auto edge: edges)
		fout << edge.first << ' ' << edge.second << '\n';
	
}

int main() {
	
	std::ifstream fin("apm.in", std::ifstream::in);
	fin >> n >> m;
	graph = std::vector<std::vector<std::pair<int,int> > >(n + 1);
	
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < m; i++) {
		fin >> tmp1 >> tmp2 >> tmp3;
		graph[tmp1].push_back(std::make_pair(tmp2, tmp3));
		graph[tmp2].push_back(std::make_pair(tmp1, tmp3));
	}

	Prim();
}