#include <bits/stdc++.h>

using namespace std;

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

struct muchie {
    int n1, n2;
    int c;
};

int n, m;
int x, y, z;
vector<muchie> g;
int tati[200001], height[200001];
vector<pair<int, int>> apm;
int cost;

int find(int i) {
    int rez = i;
    vector<int> parcurs;
    while (tati[rez] != rez) {
        parcurs.push_back(rez);
        rez = tati[rez];
    }

    for (int x : parcurs) {
        tati[x] = rez;
    }

    return rez;
}

void unire(int i, int j) {
    int r1 = find(i);
    int r2 = find(j);

    if (height[r1] > height[r2]) {
        tati[r2] = r1;
    } else {
        tati[r1] = r2;
        height[r2] = max(height[r2] + 1, height[r1]);
    }
}

void kruskal() {
    for (auto& p : g) {
        int r1 = find(p.n1);
        int r2 = find(p.n2);

        if (r1 == r2) {
            continue;
        }

        unire(p.n1, p.n2);
        cost += p.c;
        apm.push_back({ p.n1, p.n2 });
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        g.push_back({ x, y, z });
    }

    for (int i = 1; i <= n; i++) {
        tati[i] = i;
    }

    sort(g.begin(), g.end(), [](muchie p1, muchie p2) {
        return p1.c < p2.c;
    });

    kruskal();

    fout << cost << "\n";
    fout << apm.size() << "\n";
    for (auto& x : apm) {
        fout << x.first << " " << x.second << "\n";
    }
}