#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");

int n, m, n1, n2, cost, i;
vector<pair<int,pair<int,int>>>lista;
vector<int>parent;

int find(int x)
{
	while (parent[x] != x)
	{
		parent[x] = parent[parent[x]];
		x = parent[x];
	}
	return x;
}

void reuniune(int x, int y) {
	int i = find(x);
	int j = find(y);
	parent[i] = parent[j];
}


int main() {
	f >> n >> m;
	lista.resize(n+1);
	parent.resize(n + 1);
	for (int i = 1; i <= m; i++)
	{
		f >> n1 >> n2 >> cost;

		lista.push_back({ cost,{n1,n2} });
	}
	sort(lista.begin(), lista.end());

	for (i = 1; i <= n; i++)
		parent[i] = i;

	int cost_total = 0;
	vector<pair<int, int>>edges;
	for (auto el : lista)
	{
		cost = el.first;
		n1 = el.second.first;
		n2 = el.second.second;
		if (find(n1) != find(n2)) {
			cost_total += cost;
			reuniune(n1, n2);
			edges.push_back({ n1,n2 });

		}

	}
	g << cost_total << "\n";
	g << edges.size() << "\n";
	for (auto el : edges)
		g << el.first << " " << el.second << "\n";
}