#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>

#define NMAX 200003


using namespace std;

int n,m;
int tata[NMAX];

struct val {
	int x, y, cost;
};
vector<val>muchii;

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

bool cmp(val a, val b)
{
	return a.cost < b.cost;
}

int cRad(int k)
{
	int rad = k;
	while (tata[rad] > 0)
	{
		rad = tata[rad];
	}
	int nr = k;
	while (tata[nr] > 0)
	{
		int aux = nr;
		nr = tata[nr];
		tata[aux] = rad;
	}
	return rad;
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		fin >> x >> y >> c;
		muchii.push_back({ x,y,c });
	}
	stable_sort(muchii.begin(), muchii.end(), cmp);

	for (int i = 1; i <= n; i++)
	{
		tata[i] = -1;
	}

	int nrC = 1;
	int costuri = 0;
	vector<pair<int, int>>sol;
	for (int i = 0; i < muchii.size() && nrC<n; i++)
	{
		int rad1 = cRad(muchii[i].x);
		int rad2 = cRad(muchii[i].y);
		if (rad1 != rad2)
		{
			nrC ++;
			costuri += muchii[i].cost;
			sol.push_back({ muchii[i].x,muchii[i].y });
			if (tata[rad1] <= tata[rad2])
			{
				tata[rad1] += tata[rad2];
				tata[rad2] = rad1;
			}
			else {
				tata[rad2] += tata[rad1];
				tata[rad1] = rad2;
			}
		}
	}

	fout << costuri << "\n" << sol.size() << "\n";
	for (int i = 0; i < sol.size(); i++)
	{
		fout << sol[i].first << " " << sol[i].second << "\n";
	}
	return 0;
}