#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);
	}
}


int arb(int nod)
{
	while ( t[nod] )
		nod = t[nod];

	return nod;
}



void rezolv()
{
	int i, j;


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

			if ( h[a[i].x] == h[a[i].y] )
			{
				t[a[i].x] = a[i].y;
				h[a[i].y]++;
			}
			else
				if ( h[a[i].x] < h[a[i].y] )
					t[a[i].x] = a[i].y;
				else
					t[a[i].y] = a[i].x;
		}


	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;
}