#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAXN 200005
#define IN "apm.in"
#define OUT "apm.out"

typedef struct NOD{
	int cheie;
	int cost;
	struct NOD *next;
}NOD;

typedef struct {
	int a, b;
}ARC;

ARC *sol[MAXN];

NOD *graf[MAXN];

FILE *in, *out;

int n, lenSol, cost;
bool vizitat[MAXN];

void prim(){

	int i, j, min, nod1, nod2, U[MAXN], lenU = 0;
	NOD *tmp;

	vizitat[1] = true;
	U[lenU++] = 1;

	for (i = 1; i < n; ++i){
		min = INT_MAX;

		for (j = 0; j < lenU; ++j){

			tmp = graf[U[j]] -> next;
			

			while (tmp != NULL){
				if (vizitat[tmp->cheie] == false && tmp->cost < min){
					nod1 = U[j];
					nod2 = tmp->cheie;
					min = tmp->cost;
				}
				tmp = tmp -> next;
			}
		}

		U[lenU++] = nod2;
		vizitat[nod2] = true;

		sol[lenSol] = (ARC*) malloc(sizeof(ARC));

		sol[lenSol]->a = nod1;
		sol[lenSol++]->b = nod2;
		cost += min;
	}
}

int main(void){

	int i, m, a, b, c;

	in = fopen(IN, "r");

	fscanf(in, "%d%d", &n, &m);

	for (i = 1; i <= n; ++i){
		graf[i] = (NOD*) malloc(sizeof(NOD));
		graf[i]->next = NULL;
	}

	for (i = 0; i < m; ++i){
		fscanf(in, "%d%d%d", &a, &b, &c);
		NOD *tmp = (NOD*) malloc (sizeof(NOD));
		tmp->cheie = b;
		tmp->cost = c;
		tmp->next = graf[a]->next;
		graf[a]->next = tmp;

		NOD *tmp2 = (NOD*) malloc (sizeof(NOD));
		tmp2->cheie = a;
		tmp2->cost = c;
		tmp2->next = graf[b]->next;
		graf[b]->next = tmp2;
	}

	fclose(in);

	prim();

	out = fopen(OUT, "w");

	fprintf(out, "%d\n%d\n", cost, n - 1);

	for (i = 0; i < lenSol; ++i)
		fprintf(out, "%d %d\n", sol[i]->a, sol[i]->b);

	return 0;
}