#include <stdio.h>
#include <stdlib.h>
#define NMAX 1000
#define INF (1<<30)

struct graf {
    int node;
    int cost;
    struct graf *next;
};

struct graf *A[NMAX];
int viz[NMAX], h[NMAX], pi[NMAX], dist[NMAX], poz[NMAX];
int N, M, cTot, nr, size;

void swap(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void add(int what, int where, int cost)
{
    struct graf *q = malloc(sizeof(struct graf));
    q->node = what;
    q->cost = cost;
    q->next = A[where];
    A[where] = q;
}

void read()
{
    int x, y, i, cost;
    scanf("%d %d", &N, &M);
    for (i=1; i<=N; ++i) {
        dist[i] = INF;
    }
    for (i=1; i<=M; ++i) {
        scanf("%d %d %d", &x, &y, &cost);
        add(x, y, cost);
        add(y, x, cost);
    }
}

void heapUp(int what)
{
    int f;
    while (what > 1) {
        f = what>>1;
        if (dist[h[f]] > dist[h[what]]) {
	poz[h[f]] = what;
	poz[h[what]] = f;
	swap(f, what);
	what = f;
        }
        else
	what = 1;
    }
}

void heapDown(int what)
{
    int f = what;
    while (what <= size) {
        if ((what<<1) <= size) {
	f = what<<1;
	if (f+1 <= size)
	    if (dist[h[f]] > dist[h[f+1]])
	        ++f;
        }
        else
	return;
        if (dist[h[what]] > dist[h[f]]) {
	poz[h[f]] = what;
	poz[h[what]] = f;
	swap(f, what);
	what = f;
        }
        else
	return;
    }
}

void Prim()
{
    int i;
    dist[1] = 0;
    h[++size] = 1;
    for (i=2; i<=N; ++i) {
        h[++size] = i;
        poz[i] = size;
        heapUp(size);
    }

    while (size) {
        int min = h[1];
        viz[min] = 1;
        cTot += dist[min];
        ++nr;
        swap(1, size);
        --size;
        poz[h[1]] = 1;
        
        heapDown(1);
        struct graf *q = A[min];
        while (q) {
	if (!viz[q->node] && dist[q->node] > q->cost) {
	    dist[q->node] = q->cost;
	    pi[q->node] = min;
	    heapUp(poz[q->node]);
	}
	q = q->next;
        }
    }
}

int main()
{
    freopen("prim.in", "r", stdin);
    freopen("prim.out", "w", stdout);
    int i;
    read();
    Prim();
    printf("%d\n%d\n", cTot, nr-1); 
    for (i=2; i<=N; ++i) 
        printf("%d %d\n", pi[i], i);
    return 0;
}