// algoritmul lui Prim

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

using namespace std;

#define INFINITY 1001

struct Node {
    int name;
    int cost;
};

bool Read(ifstream& file, vector< list<Node> >& G, int& n) {
    int m;
    int x, y, c;

    file >> n >> m;
    cout << "read: " << n << " " << m << endl;

    if(n <= 0 || m < 0)
        return false;

    G.resize(n);

    for(int i=0; i<m; i++) {
        Node temp;
        file >> x >> y >> c;
        cout << "read: " << x << " " << y << " " << c << endl;
        temp.name = y;
        temp.cost = c;
        G[x].push_back(temp);
        temp.name = x;
        G[y].push_back(temp);
    }

    cout << endl;

    return true;
}

bool operator< (Node& a, Node& b) {
    return ( a.cost < b.cost );
}

void decrease_key(vector<Node>& heap, vector<int>& map, int name) {
    //cout << "Called decrease on " << (char)(name + 'A') << " on position " << map[name] << endl;
    int key = map[name];
    int parent = (key-1) / 2;

    if(heap[key] < heap[parent]) {
        swap(heap[key], heap[parent]);
        swap(map[ heap[key].name ], map[ heap[parent].name ]);
        //cout << "New position for " << (char)(name + 'A') << " is " << map[name] << endl;
        decrease_key(heap, map, heap[parent].name);
    }
}
void increase_key(vector<Node>& heap, vector<int>& map, int key) {
    //cout << "Called increase on " << (char)(key + 'A') << endl;

    int i = map[key];
    int n = heap.size();
    if(i >= n)
        return;

    int left = 2*i + 1;
    int right = 2*i + 2;

    int next = i;

    if(left < n && heap[left] < heap[i]) {
        swap(heap[left], heap[i]);
        swap( map[ heap[left].name ], map[ heap[i].name ] );
        next = left;
    }
    if(right < n && heap[right] < heap[i]) {
        swap(heap[right], heap[i]);
        swap( map[ heap[right].name ], map[ heap[i].name ] );
        next = right;
    }

    if(next != i) {
        //cout << "New position for " << (char)(key + 'A') << " is " << next << endl;
        increase_key(heap, map, heap[next].name);
    }
}

Node heap_pop(vector<Node>& heap, vector<int>& map) {
    Node ret = heap.front();

    swap(heap.front(), heap.back());
    swap(map[ heap.front().name ], map[ heap.back().name ]);
    heap.pop_back();
    increase_key(heap, map, heap.front().name);

    return ret;
}

bool contains(vector<Node>& heap, vector<int>& map, int name) {
    if( map[name] < heap.size() )
        return true;
    return false;
}

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    vector< list<Node> > graf;
    int n;

    if(!in)
        return 2;

    if(!Read(in, graf, n))
        return 1;

    // aici incepe algoritmul
    vector<Node> heap(n);
    vector<int> map(n);
    vector<int> parent(n);
    int sum = 0;

    // initializari
    for(int i = 0; i < n; ++i) {
        heap[i].name = i;
        heap[i].cost = INFINITY;

        map[i] = i;

        parent[i] = -1;
    }

    // se alege un nod de inceput
    int start = 0;

    heap[start].cost = 0;
    decrease_key(heap, map, start);

    while(heap.size() > 0) {
        Node u = heap_pop(heap, map);

        sum += u.cost;

        // exploram vecinii nodului
        for(list<Node>::iterator iter = graf[u.name].begin();
            iter != graf[u.name].end();
            ++iter)
        {
            if( contains(heap, map, (*iter).name) ) {
                Node& curr = heap[ map[ (*iter).name ] ];
                if( (*iter).cost < curr.cost ) {
                    curr.cost = (*iter).cost;
                    parent[curr.name] = u.name;
                    decrease_key(heap, map, (*iter).name);
                }
            }
        }
    }

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

    return 0;
}