#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>

#define dim 1000
#define OO 1000000000
using namespace std;

struct Graph {
    int N, M;
    vector< pair<int, int> > V[dim];
    int sursa[dim];
    int d[dim];
};

struct Heap {
    int size;
    int h[dim];
    int poz[dim];
    Graph *g;

    Heap(Graph *g) {
        this->g = g;
        size = 0;
    }

    void add(int index) {
        h[++size] = index;
        poz[size] = size;
        upheap(size);
    }

    void remove() {
        swap(h[1], h[size]);
        swap(poz[h[1]], poz[h[size]]);
        poz[h[size]] = -1;
        size--;
        downheap(1);
    }

    bool cmp(int pretendent, int actual) {
        return g->d[h[pretendent]] < g->d[h[actual]];
    }

    void upheap(int n) {
        int t = n >> 1;
        while (t != 0 && cmp(n, t)) {
            swap(h[n], h[t]);
            swap(poz[h[n]], poz[h[t]]);

            n = t;
            t = n >> 1;
        }
    }

    void downheap(int n) {
        int f = n << 1;
        if (f+1 <= size && cmp(f+1, f)) f++;
        while (f <= size && cmp(f, n)) {
            swap(h[n], h[f]);
            swap(poz[h[n]], poz[h[f]]);

            n = f;
            f = n << 1;
            if (f+1 <= size && cmp(f+1, f)) f++;
        }
    }

    void print() {
        printf("Heap: ");
        for (int i = 1; i <= size; i++)
            printf("%d ", h[i]);
        printf("\n");
    }
};

struct Result {
    int cost;
    int muchiiSelectate;
    vector < pair<int, int> > vMuchii;

    Result(Graph *g) {
        cost = 0;
        muchiiSelectate = g->N - 1;
    }
};

void read(Graph *g) {

    scanf("%d%d", &g->N, &g->M);

    for (int i = 1, a, b, c; i <= g->M; i++) {

        // de la a la b se duce o muchi de cost c
        scanf("%d%d%d", &a, &b, &c);
        g->V[a].push_back(make_pair(b, c));
        g->V[b].push_back(make_pair(a, c));
    }
}

void solve(Graph *g, Heap *h, Result *r) {

    g->d[1] = 0;
    h->add(1);

    for (int i = 2; i <= g->N; i++) {
        g->d[i] = OO;
        h->add(i);
    }

    while (h->size > 0) {

        //h->print();
        int nod = h->h[1];
        h->remove();

        if (h->size != g->N-1) {
            r->cost += g->d[nod];
            r->vMuchii.push_back(make_pair(nod, g->sursa[nod]));
        }

        for (int i = 0; i < g->V[nod].size(); i++) {

            int fiu = g->V[nod][i].first;
            int cost = g->V[nod][i].second;

            if (h->poz[fiu] != -1 && g->d[fiu] > cost) {

                g->sursa[fiu] = nod;
                g->d[fiu] = cost;

                if (fiu == 9 || fiu == 8)
                    fiu = fiu + fiu - fiu;

                h->upheap(h->poz[fiu]);
            }
        }
    }
}

void print(Result *r) {

    printf("%d\n%d\n", r->cost, r->muchiiSelectate);

    for (int i = 0; i < r->vMuchii.size(); i++)
        printf("%d %d\n", r->vMuchii[i].first, r->vMuchii[i].second);
}

int main() {

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

    Graph *g = new Graph();
    Heap *h = new Heap(g);

    read(g);

    Result *r = new Result(g);

    solve(g, h, r);
    print(r);
}