#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits>

using namespace std;

struct Item { //Item struktura (a, b csucspontok. g suly)
    int p;
    int g;

    Item(int w, int r) { //constructor
        p = w;
        g = r;
    }
};

struct Compare { //priority_queue osszehasonlitas
    bool operator()(Item &i1, Item &i2) {
        return i1.g > i2.g;
    }
};

const int INF = numeric_limits<int>::max() / 2;
int n;

priority_queue<Item, vector<Item>, Compare> prq;
vector<Item> *graph;

void beolvas() {
    int m, u, v, k;
    ifstream input("apm.in");
    input >> n >> m;

    graph = new vector<Item>[n + 1];

    for (int i = 0; i < m; i++) {
        input >> u >> v >> k;
        graph[u].push_back(Item(v, k));
        graph[v].push_back(Item(u, k));
    }

    input.close();
}

void prim(int r) {
    int d[n + 1], parent[n + 1];
    bool used[n + 1];

    for (int i = 1; i <= n; i++) {
        d[i] = INF;
        parent[i] = 0;
        used[i] = false;
    }

    d[r] = 0;
    prq.push(Item(r, 0));

    Item u = Item(0, 0), v = Item(0, 0);
    while (prq.size() > 0) {
        u = prq.top();
        prq.pop();

        if (used[u.p]) continue;
        used[u.p] = true;

        for (int i = 0; i < graph[u.p].size(); i++) {
            v = graph[u.p][i];

            if (!used[v.p] && v.g < d[v.p]) {
                d[v.p] = v.g;
                parent[v.p] = u.p;
                prq.push(Item(v.p, v.g));
            }
        }
    }

    ofstream out("apm.out");
    int aa = 0;
    for (int i = 1; i <= n; i++) {
        aa += d[i];
    }
    out << aa << endl;
    out << n - 1 << endl;
    for (int i = 2; i <= n; i++) {
        out << i << " " << parent[i] << "\n";
    }
}

int main() {
    beolvas();
    prim(1);

    return 0;
}