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

const int mmax=400001;
const int nmax=200001;
ifstream f("apm.in");
ofstream g("apm.out");
int grup[nmax], x[mmax], y[mmax], c[mmax], n, m, ind[mmax],ind_muchii_selectate[nmax];

bool comp(int i, int j)
{
	return c[i] < c[j];
}

int FindSet(int i)
{
	if (grup[i] == i) return i;
	grup[i] = FindSet(grup[i]);
	return grup[i];
}

void Union(int i, int j)
{
	grup[FindSet(i)] = FindSet(j);
}

int main()
{
	int i;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x[i] >> y[i] >> c[i];
		ind[i] = i;
	}
	for (i = 1; i <= n; i++)
		grup[i] = i;


	sort(ind + 1, ind + m + 1, comp);

	int suma = 0, K = 0;
	for (i = 1; i <= m; i++)
	{
		if (FindSet(x[ind[i]]) != FindSet(y[ind[i]]))
		{
			suma += c[ind[i]];
			Union(x[ind[i]], y[ind[i]]);
			ind_muchii_selectate[++K] = ind[i];
		}
	}
	g << suma << "\n";
	g << n - 1 << "\n";
	for (i = 1; i <= n - 1; i++)
		g << x[ind_muchii_selectate[i]] << " " << y[ind_muchii_selectate[i]] << "\n";
	return 0;
}