#include <bits/stdc++.h>

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

const int NMAX = 2e5 + 5;
const int MMAX = 4e5 + 5;

int n, m;
struct element {
    int x, y, cost;
} edges[MMAX];

struct DSU {
    int rep[NMAX];
    int sizee[NMAX];

    DSU(int n) {
        for (int i = 1; i <= n; i++) {
            rep[i] = i;
            sizee[i] = 1;
        }
    }

    int get_rep(int a) {
        if (rep[a] == a) return a;
        return rep[a] = get_rep(rep[a]);
    }

    bool same_set(int a, int b) {
        int ra = get_rep(a);
        int rb = get_rep(b);
        return ra == rb;
    }

    void join(int a, int b) {
        int ra = get_rep(a);
        int rb = get_rep(b);

        if (ra == rb) return;

        if (sizee[ra] < sizee[rb]) swap(ra, rb);

        rep[rb] = ra;
        sizee[ra] += sizee[rb];
    }
};

void Kruskal() {
    DSU dsu(n);
    sort(edges, edges + m, [](const element &a, const element &b) {
         return a.cost < b.cost;
    });

    long long ans = 0;
    vector<pair<int, int>> sol;
    for (int i = 0; i < m; i++) {
        if (!dsu.same_set(edges[i].x, edges[i].y)) {
            dsu.join(edges[i].x, edges[i].y);
            ans += edges[i].cost;
            sol.push_back(make_pair(edges[i].x, edges[i].y));
        }
    }

    fout << ans << '\n';
    fout << n - 1 << '\n';
    for (auto it : sol) {
        fout << it.first << ' ' << it.second << '\n';
    }
}

int main()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y, cost;
        fin >> x >> y >> cost;
        edges[i] = {x, y, cost};
    }

    Kruskal();
    return 0;
}