#include<cstdio>
#include<algorithm>

using namespace std;

#define nMax 200001

int n, m, s;
int q[nMax];

struct muchie {
	int x, y, cost;
	} v[nMax], z[nMax];

int cmp(const void *x, const void *y)
{
    muchie a=*((muchie *)x);
    muchie b=*((muchie *)y);
    return a.cost - b.cost;
}

void inPut()
{
	freopen ( "apm.in", "r", stdin );
	scanf ( "%d %d", &n, &m );
	
	for(int i=1; i<=m; i++)
		scanf ( "%d %d %d", &v[i].x, &v[i].y, &v[i].cost );
	fclose(stdin);
	qsort ( v+1, m, sizeof(muchie), cmp );
}

int main()
{
	inPut();
	for(int i=1; i<=n; i++)
		q[i] = i;

	int k=1, t;

	for(int i=1; i<n; i++)
	{
		while ( q[ v[k].x ] == q[ v[k].y ] )
			++k;
		t = q[ v[k].y ];

		for(int j=1; j<=n; j++)
			if ( q[j] == t )
				q[j] = q[ v[k].x ];
		
		z[i].x = v[k].x;
		z[i].y = v[k].y;

		s += v[k].cost;
	}

	freopen ( "apm.out", "w", stdout );
	
	printf ( "%d\n%d\n", s, n-1 );
	for(int i=1; i<n; i++)
		printf ( "%d %d\n", z[i].x, z[i].y );

	fclose(stdout);
	return 0;
}