// http://infoarena.ro/problema/apm

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

#define INF INT_MAX
#define NMAX 200010

int Heap[NMAX], Pos[NMAX], Cost[NMAX];
int hsz = 0;

inline int cmp(int a, int b) { // a = parintele lui b
	return (Cost[a] < Cost[b]);
}
inline void swap(int *a, int *b) {
	int c = *a;
	*a = *b;
	*b = c;
}

void swim(int p) { // bubble-up
	while (p / 2 >= 1 && !cmp(Heap[p / 2], Heap[p])) {
		swap(&Heap[p], &Heap[p / 2]);
		swap(&Pos[Heap[p]], &Pos[Heap[p / 2]]);
		p /= 2;
	}
	Pos[Heap[p]] = p;
}

void sink(int p) { // bubble-down
	int j;
	while (2 * p <= hsz) {
		j =  2 * p;
		if (j + 1 <= hsz && !cmp(Heap[j], Heap[j + 1]))
			++ j;
		if (!cmp(Heap[p], Heap[j])) {
			swap(&Heap[p], &Heap[j]);
			swap(&Pos[Heap[p]], &Pos[Heap[j]]);
			p = j;
		} else
			break;
	}
}

void heapInsert(int i) {
	Heap[++ hsz] = i;
	Pos[i] = hsz;
	swim(hsz);
}

int heapPop() {
	int temp = Heap[1];
	Pos[Heap[hsz]] = 1;
	swap(&Heap[hsz], &Heap[1]);
	-- hsz;
	sink(1);
	return temp;
}

void heapChangePriority(int newPriority, int p) {
	int shouldSink = newPriority > Cost[Heap[p]]; // !cmp == true
	Cost[Heap[p]] = newPriority;
	if (shouldSink)
		sink(p);
	else
		swim(p);
}

typedef struct {
	int b, cost;
} pair;

pair **Next; // vecinii fiecarui nod
int *numNext, // numarul de vecini ai fiecarui nod
    n, m; // numarul de noduri / muchii
inline void nodeAdd(int a, int b, int cost) {
	Next[a] = (pair*)realloc(Next[a], (numNext[a] + 1) * sizeof(pair));
	pair newPair; newPair.b = b, newPair.cost = cost;
	Next[a][numNext[a] ++ ] = newPair;
}

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

	scanf("%d%d", &n, &m);
	Next = (pair**)calloc(n, sizeof(pair*));
	numNext = (int*)calloc(n, sizeof(int));
	int *Used = (int*)calloc(n, sizeof(int)),
	    *Pred = (int*)calloc(n, sizeof(int));

	int i, a, b, c;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d%d", &a, &b, &c);
		nodeAdd(a - 1, b - 1, c);
		nodeAdd(b - 1, a - 1, c);
	}
	
	// ** algoritmul lui Prim
	
	// 1. introduc fiecare nod in heap
	Cost[0] = 0;
	heapInsert(0); // aleg sa pornesc din primul nod
	for (i = 1; i < n; ++ i) {
		Cost[i] =  INF;
		Used[i] = 0;
		heapInsert(i);
	}

	int u;
	pair next;
	// 2. ciclul principal
	while (hsz > 0) {
		/*for (i = 1; i <= hsz; ++ i)
			fprintf(stderr, "%d ", Cost[Heap[i]]);
		fprintf(stderr, "\n");*/

		u = heapPop();
			Used[u] = 1;
		for (i = 0; i < numNext[u]; ++ i) {
			next = Next[u][i];
			if (!Used[next.b] && Cost[next.b] > next.cost) {
				Cost[next.b] = next.cost;
				heapChangePriority(Cost[next.b], Pos[next.b]);
				Pred[next.b] = u;
			}
		}
	}
	int cost = 0;
	for (i = 1; i < n; ++ i)
		cost += Cost[i];

	// 3. afisare
	printf("%d\n%d\n", cost, n - 1);
	for (i = 1; i < n; ++ i)
		printf("%d %d\n", i + 1, Pred[i] + 1);
	// **

	for (i = 0; i < n; ++ i)
		free(Next[i]);
	free(Next);
	free(numNext);
	free(Pred);
	free(Used);
	return 0;
}