#include <stdio.h>

#define NMAX 200001
#define MMAX 400001

int N, M, h[NMAX], t[NMAX], m1[NMAX], m2[NMAX], nrm, s;

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

muchie a[MMAX];

int partitie(int st, int dr)
{
	int i, j, pivot;
	muchie aux;

	i = st - 1;
	j = dr + 1;
	pivot = a[ ( st + dr ) / 2].c;

	while (1)
	{
		do { ++i; } while ( a[i].c < pivot);
		do { --j; } while ( a[j].c > pivot);

		if ( i < j)
		{
			aux = a[i];
			a[i] = a[j];
			a[j] = aux;
		}
		else
			return j;
	}
}


void sort(int st, int dr)
{
	int m;
	if ( st < dr)
	{
		m = partitie(st, dr);
		sort(st, m);
		sort(m + 1, dr);
	}
}

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

	if ( h[x] == h[y])
		h[y]++;
}

int gaseste(int nod)
{
	if (nod != t[nod] )
		t[nod] = gaseste(t[nod]);

	return t[nod];
}

void rezolv()
{
	int i, j, tx, ty;

	for ( i = 1; i <= N; i++)
		t[i] = i;

	for ( i = 1; i <= M && nrm < N - 1; i++)
	{
		tx = gaseste(a[i].x);
		ty = gaseste(a[i].y);
		if (  tx != ty )
		{
			s += a[i].c;
			nrm++;
			m1[nrm] = a[i].x;
			m2[nrm] = a[i].y;

			uneste(tx, ty);
		}
	}

	printf("%d\n%d\n", s, nrm);

	for ( i = 1; i <= nrm; i++)
		printf("%d %d\n", m1[i], m2[i]);
}

int main()
{
	int i;

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

	scanf("%d %d", &N, &M);

	for ( i = 1; i <= M; i++)
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].c);
		
	sort(1, M);

	rezolv();


	return 0;
}