#include<cstdio>
#include<algorithm>
#define M_MAX 400000
#define N_MAX 200000
using namespace std;

struct muchie
{
	int x, y, cost;
};

struct Vector
{
	int x, y;
};

muchie v[M_MAX + 1];
Vector s[M_MAX];
int p[N_MAX + 1], n, m, cost, nrm;

bool cmp(muchie a, muchie b)
{
	if (a.cost < b.cost) return true;
	return false;
}

void Read()
{
	FILE *fin = fopen("apm.in", "r");
	fscanf(fin, "%d%d", &n, &m);
	for (int i = 0; i<m; i++)
		fscanf(fin, "%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
	fclose(fin);
}

void Init()
{
	for (int i = 1; i <= n; i++)
		p[i] = i;
}

int Find(int x)
{
	int r = x, aux;
	while (p[r] != r)
		r = p[r];
	while (p[x] != r)
	{
		aux = p[x];
		p[x] = r;
		x = aux;
	}
	return r;
}

void APM()
{
	int i, RootX, RootY;
	for (i = 0; i<m; i++)
	{
		RootX = Find(v[i].x);
		RootY = Find(v[i].y);
		if (RootX != RootY)
		{
			p[RootX] = RootY;
			cost += v[i].cost;
			s[nrm].x = v[i].x;
			s[nrm++].y = v[i].y;
		}
	}
}

void Write()
{
	FILE *fout = fopen("apm.out", "w");
	fprintf(fout, "%d\n%d\n", cost, nrm);
	for (int i = 0; i<nrm; i++)
		fprintf(fout, "%d %d\n", s[i].x, s[i].y);
	fclose(fout);
}

int main()
{
	Read();
	Init();
	sort(v, v + m, cmp);
	APM();
	Write();
}