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

struct Edge {
    int w, x, y; //w-> weight; xy capetele muchiei
};

bool comp(Edge e1, Edge e2) {
    return e1.w < e2.w;
}

int *t, *h; //vectorul de tati, respectiv de intaltimi pt padurea de inmultiri disjuncte

void Init(int n) {
    t = new int [n + 1];
    h = new int [n + 1];
    for (int i = 1; i <= n; ++i) {
        t[i] = h[i] = 0;
    }
}

int Reprez(int x) {
    if (t[x] == 0) {
        return x;
    }
    return Reprez(t[x]);
}

void Union(int x, int y) {
    x = Reprez(x);
    y = Reprez(y);
    if (h[x] < h[y]) {
        t[x] = y;
        return;
    }
    t[y] = x;

    if (h[x] == h[y]) {
        h[x]++;
    }
}

std::list<Edge> Edges, T;
int n, m, cost; //nr noduri, nr muchii, cost

int main() {
    std::ifstream fin{ "apm.in" };
    fin >> n;
    fin >> m;
    Init(n);

    for (int i = 0; i < m; i++) {
        Edge e;
        fin >> e.x >> e.y >> e.w;
        Edges.push_back(e);
    }

    Edges.sort(comp); // <- preprocesare Kruskal

    for (Edge e : Edges) {
        if (T.size() == n-1) break;

        int x, y;
        x = Reprez(e.x);
        y = Reprez(e.y);

        if (x != y) {
            T.push_back(e);
            cost += e.w;
            Union(x, y);
        }
    }

    std::ofstream fout{ "apm.out" };
    fout << cost << std::endl;
    fout << T.size() << std::endl;

    for (Edge e : T) {
        fout << e.y << " " << e.x << std::endl;
    }

    fout.close();
    fin.close();
    return 0;
}