#include <bits/stdc++.h>
#define INFILE "apm.in"
#define OUTFILE "apm.out"
#define DIM 200005

using namespace std;

ifstream f(INFILE);
ofstream g(OUTFILE);

struct Edge {
    int x, y, cost;

    bool operator <(const Edge a) {
        return cost < a.cost;
    }
};

int n, m, ansCost, t[DIM];
vector <Edge> edges, solEdges;

void init() {
    for (int i = 1; i <= n; i++) {
        t[i] = i;
    }
}

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

void leaga(Edge edge) {
    t[radacina(edge.x)] = t[radacina(edge.y)];
    solEdges.push_back(edge);
    ansCost += edge.cost;
}

int main() {

    f >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    sort(edges.begin(), edges.end());

    init();
    for (auto edge: edges) {
        int radx = radacina(edge.x);
        int rady = radacina(edge.y);

        if (radx != rady) {
            leaga(edge);
        }
    }

    g << ansCost << "\n" << n - 1 << "\n";
    for (auto sol: solEdges) {
        g << sol.x << " " << sol.y << "\n";
    }

    return 0;
}