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

using namespace std;

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

vector<int> t;

int find(int x)
{
	if (t[x] == 0)
	{
		return x;
	}

	t[x] = find(t[x]);
	return t[x];
}

void unite(int x, int y)
{
	int rx = find(x);
	int ry = find(y);
	t[rx] = ry;
}

int main()
{
	int n, m;
	fin >> n >> m;

	t.resize(n + 1);
	vector<pair<int, pair<int, int>>> drumuri(m);

	for (int i = 0; i < m; i++)
	{
		int x, y, cost;
		fin >> x >> y >> cost;

		drumuri[i] = { cost, { x, y } };
	}

	sort(drumuri.begin(), drumuri.end());

	vector<pair<int, int>> muchii;
	int CostMin = 0;

	for (auto drum : drumuri)
	{
		int cost = drum.first;
		int x = drum.second.first;
		int y = drum.second.second;

		if (find(x) != find(y))
		{
			CostMin += cost;
			muchii.push_back({ x, y });
			unite(x, y);
		}
	}

	fout << CostMin << '\n' << n - 1 << '\n';
	for (auto muchie : muchii)
	{
		fout << muchie.first << ' ' << muchie.second << '\n';
	}

	return 0;
}

/*

	

*/