#include <algorithm>
#include <fstream>
#include <vector>

#include <iostream>

using namespace std;

struct Edge
{
	int a, b, cost;
};

using Graph = vector<Edge>;

int Root(vector<int> &fa, int node)
{
	if (fa[node] == -1) {
		return node;
	}
	return (fa[node] = Root(fa, fa[node]));
}

void Unite(vector<int> &fa, int a, int b)
{
	int ra = Root(fa, a);
	int rb = Root(fa, b);
	if (ra != rb) {
		fa[rb] = ra;
	}
}

pair<int, vector<pair<int, int>>> FindMst(Graph &g, int n)
{
	sort(g.begin(), g.end(), [](const Edge &a, const Edge &b) -> bool {
		return a.cost < b.cost;
	});

	vector<int> fathers(n + 1, -1);
	int total_cost = 0;

	vector<pair<int, int>> mst(n - 1);
	int nmst = 0;

	int nedges = 0;
	for (int i = 1; i < n; ++i) {
		while (Root(fathers, g[nedges].a) == Root(fathers, g[nedges].b)) {
			++nedges;
		}

		total_cost += g[nedges].cost;
		mst[nmst++] = {g[nedges].a, g[nedges].b};

		Unite(fathers, g[nedges].a, g[nedges].b);
		++nedges;		
	}	
	return {total_cost, mst};
}

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

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

	Graph graph(m);
	for (int i = 0; i < m; ++i) {
		fin >> graph[i].a >> graph[i].b >> graph[i].cost;
	}	

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

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

	return 0;
}