#include <fstream>
#include <queue>
#include <vector>

#include <iostream>

using namespace std;

using Pair = pair<int, int>;
using Graph = vector<vector<Pair>>;

const int kInf = (1 << 25);

pair<int, vector<Pair>> FindMst(const Graph &g)
{
	priority_queue<Pair, vector<Pair>, greater<Pair>> q;
	q.push({-kInf, 0});

	vector<int> min_cost(g.size(), kInf);
	min_cost[0] = -kInf;

	vector<int> predecessor(g.size(), -1);
	int total_cost = 0;

	vector<bool> used(g.size(), false);
	vector<Pair> mst(g.size() - 1);
	int nmst = 0;

	for (unsigned i = 0; i < g.size(); ++i) {
		int node = -1;
		int cost = -1;
		do {
			node = q.top().second;
			cost = q.top().first;
			q.pop();
		} while (cost != min_cost[node] || used[node]);

		used[node] = true;
		if (predecessor[node] != -1) {
			mst[nmst++] = {node, predecessor[node]};
			total_cost += cost;
		}

		for (const auto &edge : g[node]) {
			int next = edge.first;
			if (edge.second < min_cost[next]) {
				min_cost[next] = edge.second;
				predecessor[next] = node;
				q.push({edge.second, next});
			}
		}
	}
	return {total_cost, mst};
}

int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");

	int n, m;
	fin >> n >> m;

	Graph graph(n);
	while (m--) {
		int x, y, c;
		fin >> x >> y >> c;
		graph[x - 1].push_back({y - 1, c});
		graph[y - 1].push_back({x - 1, c});
	}	

	auto res = FindMst(graph);
	fout << res.first << "\n" << n - 1 << "\n";

	for (const auto &edge : res.second) {
		fout << edge.first + 1 << " " << edge.second + 1 << "\n";
	}

	return 0;
}