#include <iostream>
#include <fstream>
#include <list>
#include <vector>

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;

        if(l >= n_heap)
            return;

        int i_min = i;
        if(heap[l].cost < heap[i_min].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) {
        if(x < 0 || x >= n) {
            if(x == 8)
                cout << "node 9 err" << endl;
            return false;
        }

        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(ifstream& file, vector< list<node> >& G) {
    int n, m;
    int x, y, c;

    file >> n >> m;

    G.resize(n);

    for(int i=0; i<m; i++) {
        node temp;
        file >> x >> y >> c;
        --x; --y;
        temp.name = y;
        temp.cost = c;
        G[x].push_back(temp);
        temp.name = x;
        G[y].push_back(temp);
    }
}

int main() {
    const int max_n = 200200;

    vector< list<node> > g;
    ifstream in("apm.in");
    ofstream out("apm.out");
    int sum = 0;

    read(in, 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;
            }
        }
    }

    out << sum << endl;
    out << n-1 << endl;
    for(int i = 1; i < n; ++i) {
        out << i+1 << " " << p[i] + 1 << endl;
    }

    delete[] p;

    return 0;
}