#include <fstream>

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

const int MAXN = 200'000;
const int MAXM = 400'000;

int n, m, minedge[MAXN];
long long rez;
char viz[MAXM];

struct Edge {
    int u, v, cost;
} edges[MAXM];

struct DSU {
    int sef[MAXN], cate_comp;
    
    void init(int n) {
        int i;
        cate_comp = n;
        for (i = 0; i < n; i++) {
            sef[i] = i;
        }
    }
    
    int find(int i) {
        if (i == sef[i]) {
            return i;
        }
        return sef[i] = find(sef[i]);
    }
    
    void join(int i, int j) {
        if ((i = find(i)) != (j = find(j))) {
            cate_comp--;
            sef[j] = i;
        }
    }
} dsu;

void readGraph() {
    int i;
    fin >> n >> m;
    for (i = 0; i < m; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
        edges[i].u--;
        edges[i].v--;
    }
}

void resetComps() {
    int i;
    for (i = 0; i < n; i++) {
        minedge[i] = -1;
    }
}

// este muchia a mai buna ca muchia b?
int better(int a, int b) {
    if (b == -1) {
        return 1;
    }
    return edges[a].cost < edges[b].cost;
}

void processEdges() {
    int i, u, v;
    for (i = 0; i < m; i++) {
        if (viz[i] == 0) { // daca n-am folosit muchia deja
            u = dsu.find(edges[i].u);
            v = dsu.find(edges[i].v);
            if (u != v) { // sa nu fie in aceeasi componenta
                if (better(i, minedge[u])) { // cautam cea mai buna muchie pentru fiecare componenta
                    minedge[u] = i;
                }
                if (better(i, minedge[v])) {
                    minedge[v] = i;
                }
            }
        }
    }
}

void processComps() {
    int i, u, v;
    for (i = 0; i < n; i++) { // trecem prin fiecare componenta
        if (minedge[i] != -1 // daca am gasit o muchie pentru componenta in care i e parinte
                             // daca i nu e parintele unei componente atunci nu o sa fie gasita nicio muchie
            && viz[minedge[i]] == 0) { // sa nu o fi folosit pentru componenta cu care ne unim deja
            dsu.join(edges[minedge[i]].u, edges[minedge[i]].v); // unim componentele
            rez += edges[minedge[i]].cost; // adunam costul
            viz[minedge[i]] = 1; // am folosit muchia
        }
    }
}

void findMST() {
    int i, u, v;
    
    dsu.init(n);
    rez = 0;
    while (dsu.cate_comp > 1) { // cat timp nu e arbore
        resetComps(); // resetam componentele
        processEdges(); // trecem prin fiecare muchie
        processComps(); // unim fiecare componenta cu muchia ei cea mai buna
    }
    
    fout << rez << "\n" << n - 1 << "\n"; // un arbore are n - 1 muchii
    for (i = 0; i < m; i++) {
        if (viz[i]) { // daca am folosit muchia o afisam
            fout << edges[i].u + 1 << " " << edges[i].v + 1 << "\n";
        }
    }
}

int main() {
    readGraph();
    findMST();
    return 0;
}