#include<fstream>
using namespace std;
int v1[400100], v2[400100], cost[400100], h[400100], parinte[200100], s[200100];
void qs(int i, int j)
{
	int s = i, d = j, aux, piv = h[(i + j) >> 1];
	while(s <= d)
	{
		while(cost[h[s]] < cost[piv])
			s++;
		while(cost[h[d]] > cost[piv])
			d--;
		if(s <= d)
		{
			aux = h[d];
			h[d] = h[s];
			h[s] = aux;
			s++;
			d--;
		}
	}
	if(s < j)
		qs(s, j);
	if(i < d)
		qs(i, d);
}
int main()
{
	int su = 0, n, m, x, y, c, cx, cy, i;
	ifstream f;
	f.open("apm.in");
	ofstream g;
	g.open("apm.out");
	f >> n >> m;
	for(i = 1; i <= m; i++)
	{
		f >> v1[i] >> v2[i] >> cost[i];
		h[i] = i;
	}
	for(i = 1; i <= n; i++)
		parinte[i] = i;
	qs(1, m);
	for(i = 1; i <= m && s[0] < n - 1; i++)
	{
		cx = 0;
		cy = 0;
		x = v1[h[i]];
		y = v2[h[i]];
		while(x != parinte[x])
		{
			x = parinte[x];
			cx++;
		}
		while(y != parinte[y])
		{
			y = parinte[y];
			cy++;
		}
		if(x != y)
		{
			if(cx > cy)
				parinte[y] = x;
			else
				parinte[x] = y;
			s[++s[0]] = h[i];
			su += cost[h[i]];
		}
	}
	g << su << endl;
	g << n-1 << endl;
	for(i = 1; i <= n - 1; i++)
		g << v2[s[i]] << ' ' << v1[s[i]] << endl;
	return 0;
}