#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIMN 200005
#define DIMM 400005

int N, M, Nr, Cost, R1[DIMN], R2[DIMN], T[DIMN];
struct muc { int x, y, c; } A[DIMM];

int cmp (muc x, muc y)
{
	return x.c < y.c;
}

int rad (int f)
{
	if (T[f] < 0) return f;
	return rad (T[f]);
}

void citire ()
{
	scanf ("%d%d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		scanf ("%d%d%d", &A[i].x, &A[i].y, &A[i].c);
	}
	sort (A, A + M, cmp);	
}

void paduri ()
{
	for (int i = 1; i <= N; i++)
		T[i] = -1;
	for (int i = 0, r1, r2; i < M && Nr < N - 1; i++)
	{
		r1 = rad (A[i].x);
		r2 = rad (A[i].y);
		if (r1 != r2)
		{
			Nr++;
			Cost += A[i].c;
			R1[Nr] = A[i].x;
			R2[Nr] = A[i].y;
			if (T[r1] < T[r2])
			{			
				T[r1] += T[r2];
				T[r2] = r1;
			}
			else
			{
				T[r2] += T[r1];
				T[r1] = r2;
			}
		}
	}
}	

void afisare ()
{
	printf ("%d\n%d\n", Cost, Nr);
	for (int i = 1; i <= Nr; i++)
		printf ("%d %d\n", R1[i], R2[i]);	
}

int main ()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	citire ();
	paduri ();
	afisare ();	
	
	return 0;
}