#include <fstream>
#include <algorithm>
using namespace std;

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

struct el
{
	int x, y, c;
	bool operator < (const el &alt) const
	{
		return c < alt.c;
	}
} much[400001];
bool marc[400001];

int t[200001], h[200001];

void uneste (int x, int y)
{
	if (h[x] < h[y])
		t[x] = y;
	else
	{
		t[y] = x;
		if (h[x] == h[y])
			h[x]++;
	}
}

int cauta (int x)
{
	int r, y;
	r = x;
	while (t[r])
		r = t[r];
	while (x != r)
	{
		y = t[x];
		t[x] = r;
		x = y;
	}
	return r;
}

int main()
{
	int n, m, i, x, y, rasp = 0;
	fin >> n >> m;
	for (i = 1; i<=m; i++)
		fin >> much[i].x >> much[i].y >> much[i].c;
	sort(much+1, much+m+1);
	for (i = 1; i<=m; i++)
	{
		x = cauta (much[i].x);
		y = cauta (much[i].y);
		if (x != y)
		{
			rasp = rasp + much[i].c;
			uneste (x, y);
			marc[i] = 1;
		}
	}
	fout << rasp << '\n' << n - 1 << '\n';
	for (i = 1; i<=m; i++)
		if (marc[i] == 1)
			fout << much[i].x << ' ' << much[i].y << '\n';
	return 0;
}