#include <cstdio>
#include <algorithm>
#define mmax 400010
#define nmax 200010

using namespace std;

struct muchie
{
	int x, y, c;
}a[mmax];

int n, m, cost, sol[nmax], tata[nmax], k;

bool cmp(muchie a, muchie b)
{
	if (a.c<b.c)
		return 1;
	return 0;
}

void citire()
{
	int i;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++)
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
	for (i = 1; i <= n; i++)
	{
		tata[i] = i;
	}
}

int radacina(int x)
{
	int rx = x;
	while (tata[rx] != rx)
		rx = tata[rx];
	while (tata[x] != x)
	{
		int aux = tata[x];
		tata[x] = rx;
		x = aux;
	}
	return rx;
}

void reuniune(int rx, int ry)
{
	tata[ry] = rx;
}

void APM()
{
	int i,rx,ry;
	muchie m;
	for (i = 1; k<n - 1; i++)
	{
		m = a[i];
		rx = radacina(m.x);
		ry = radacina(m.y);
		if (rx != ry)
		{
			cost += m.c;
			reuniune(rx,ry);
			sol[++k] = i;
		}
	}
}

void afisare()
{
	int i;
	printf("%d\n%d\n", cost, k);
	for (i = 1; i <= k; i++)
		printf("%d %d\n", a[sol[i]].y, a[sol[i]].x);
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	citire();
	sort(a + 1, a + m + 1, cmp);
	APM();
	afisare();

	return 0;
}