#include <iostream>
#include <list>
#include <vector>
#include <cstdio>

using namespace std;

#define INFINITY 200200

struct node {
    int name;
    int cost;
};

class heap_map {
    node* heap;
    int* map;
    int n_heap;
    int n;

public:
    heap_map() : heap(NULL), map(NULL), n_heap(0), n(0) {}
    heap_map(int N) : heap(new node[N]), map(new int[N]), n_heap(N), n(N) {
        for(int i = 0; i < n; ++i) {
            heap[i].name = i;
            heap[i].cost = INFINITY;
            map[i] = i;
        }
    }
    ~heap_map() {
        if(heap)
            delete[] heap;
        if(map)
            delete[] map;
    }

    node peek() {
        return heap[0];
    }

    bool pop() {
        if(n_heap <= 0) {
            return false;
        }

        --n_heap;
        map[ heap[n_heap].name ] = 0;
        map[ heap[0].name ] = n_heap;
        heap[0] = heap[n_heap];

        if(n_heap)
            move_down(0);

        return true;
    }

    void move_down(int i) {
        int l = 2*i + 1;
        int r = 2*i + 2;
        int i_min = i;

        if(l < n_heap && heap[l].cost < heap[i].cost)
            i_min = l;
        if(r < n_heap && heap[r].cost < heap[i_min].cost)
            i_min = r;

        if(i == i_min)
            return;

        node temp = heap[i_min];
        heap[i_min] = heap[i];
        heap[i] = temp;

        map[ heap[i_min].name ] = i_min;
        map[ heap[i].name ] = i;

        move_down(i_min);
    }

    void move_up(int i) {
        int p = (i-1)/2;

        if(heap[i].cost < heap[p].cost) {
            node temp = heap[p];
            heap[p] = heap[i];
            heap[i] = temp;

            map[ heap[i].name ] = i;
            map[ heap[p].name ] = p;

            move_up(p);
        }
    }

    bool reduce_cost(int x, int new_cost) {
        int i = map[ x ];
        if(i >= n_heap)
            return false;

        if(new_cost < heap[i].cost) {
            heap[i].cost = new_cost;
            move_up(i);
            return true;
        }

        return false;
    }
};


void read(vector< list<node> >& G) {
    int n, m;
    int x, y, c;

    FILE* in = fopen("apm.in", "r");

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

    G.resize(n);

    for(int i=0; i<m; i++) {
        node temp;
        fscanf(in, "%d %d %d", &x, &y, &c);
        --x; --y;
        temp.name = y;
        temp.cost = c;
        G[x].push_back(temp);
        temp.name = x;
        G[y].push_back(temp);
    }

    fclose(in);
}

int main() {
    const int max_n = 200200;

    vector< list<node> > g;
    int sum = 0;

    read(g);

    int n = g.size();

    heap_map hm(n);
    int* p = new int[n];

    for(int i = 0; i < n; ++i)
        p[i] = -1;

    // algortim
    int start = 0;
    hm.reduce_cost(start, 0);

    for(int step = 0; step < n; ++step) {
        node curr = hm.peek();
        hm.pop();

        sum += curr.cost;

        for(list<node>::iterator it = g[curr.name].begin(); it != g[curr.name].end(); ++it) {
            if( hm.reduce_cost(it->name, it->cost) ) {
                p[it->name] = curr.name;
            }
        }
    }

    FILE* out = fopen("apm.out", "w");

    fprintf(out, "%d\n%d\n", sum, n-1);
    for(int i = 1; i < n; ++i)
        fprintf(out, "%d %d\n", p[i], i);

    fclose(out);

    delete[] p;

    return 0;
}